𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the girth of hamiltonian weakly pancyclic graphs

✍ Scribed by Bollob�s, B�la; Thomason, Andrew

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
130 KB
Volume
26
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. In answer to a question of Erdős, we show that a Hamiltonian weakly-pancyclic graph of order n can have girth as large as about 2 n/ log n. In contrast to this, we show that the existence of a cycle of length at most 2 √ n -1 is already implied by the existence of just two long cycles, of lengths n and n -1. Moreover we show that any graph, Hamiltonian or otherwise, which has n + c edges will have girth of order at most (n/c) log c.

📜 SIMILAR VOLUMES

On the structure of extremal graphs of h
On the structure of extremal graphs of high girth
✍ Lazebnik, Felix; Wang, Ping 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 1 views

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present sev

A short proof of a theorem on Hamiltonia
A short proof of a theorem on Hamiltonian graphs
✍ Ainouche, A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB 👁 1 views

In this note, w e give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that for any independent set {u, u , w}, then G is hamiltonian. 0 1996 John

The circular chromatic number of series-
The circular chromatic number of series-parallel graphs with large girth
✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

On the linear arboricity of planar graph
On the linear arboricity of planar graphs
✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

Various results on the toughness of grap
Various results on the toughness of graphs
✍ Broersma, Hajo; Engbers, Erik; Trommel, Huib 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

Let G be a graph and let t Ն 0 be a real number. Then, We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on (G), we give some sufficient degree conditions implying that (G) Ն t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares.

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their