✦ LIBER ✦

On the structure of extremal graphs of high girth

✍ Scribed by Lazebnik, Felix; Wang, Ping

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 117 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199711)26:3<147::aid-jgt5>3.0.co;2-r

No coin nor oath required. For personal study only.

✦ Synopsis

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 several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ 2 a 2 +a+1 n a , where a = n -3 -n-2 4 , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26.

📜 SIMILAR VOLUMES

On the girth of hamiltonian weakly pancy

On the girth of hamiltonian weakly pancyclic graphs

✍ Bollob�s, B�la; Thomason, Andrew 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

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

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 quadrilaterals in layers of the cube

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

✍ Schelp, Richard H.; Thomason, Andrew 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 1 views

Erdős has conjectured that every subgraph of the n-cube Q n having more than (1/2+o(1))e(Q n ) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k -1, k and k + 1, where we are thinking of the vertices of Q n as being

On the structure of graphs with a unique

On the structure of graphs with a unique k-factor

✍ Petra Johann 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

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.