Cycles in 2-connected graphs

DOI10.1016/J.JCTB.2004.09.003MaRDI QIDQ705891zbMATH OpenOpenAlexFDO

Authors Pei Wang, Genghua Fan, Xue-Zheng Lv

Publication date 16 February 2005

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2004.09.003

zbMATH Keywords

2-connected graphscyclesextremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

\textit{P. Erdös} and \textit{T. Gallai} [Acta Math. Acad. Sci. Hung. 10, 337--356 (1959; Zbl 0090.39401)] showed that for any integer \(c\geq 2,\) if \(G\) is a graph on \(n\) vertices with more than \(c(n-1)/2\) edges, then \(G\) contains a cycle of length more than \(c\). Woodall conjectured that if \(2\leq c\leq n-1,\) and \(G\) is a 2-connected graph on \(n\) vertices with more than \(\max \{f(n,2,c),f(n,\left\lfloor c/2\right\rfloor ,c)\}\) edges, then \(G\) contains a cycle of length more than \(c,\) where \(f(n,t,c)=\binom{c+1-t}{2}+t(n-c-1+t).\) In the paper the above conjecture of Woodall is confirmed.

Recommendations

• On a conjecture of Woodall
• scientific article; zbMATH DE number 147638
• scientific article; zbMATH DE number 3914359
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• scientific article; zbMATH DE number 3908470

Cites work

• Maximal circuits of graphs. I
• Maximal cycles in graphs
• On maximal paths and circuits of graphs
• Subgraph coverings and edge switchings
• Sufficient Conditions for Circuits in Graphs^†

Cited in

(23)

• Cycles of length 2 modulo 3 in graphs
• Graphs with almost all edges in long cycles
• On a conjecture of Woodall
• The codiameter of a 2-connected graph
• Cycles and stability
• Stability of Woodall's theorem and spectral conditions for large cycles
• 2-Walk linear graphs with small number of cycles
• scientific article; zbMATH DE number 3914359 (Why is no real title available?)
• scientific article; zbMATH DE number 147638 (Why is no real title available?)
• Spectral radius and Hamiltonian properties of graphs
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Graphs with cyclomatic number two having panconnected square
• Vertex-dominating cycles in 2-connected bipartite graphs
• scientific article; zbMATH DE number 6471182 (Why is no real title available?)
• Ordering Q-indices of graphs: given size and circumference
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• The Number of Cliques in Graphs Covered by Long Cycles
• The maximum number of cliques in graphs with prescribed order, circumference and minimum degree
• How connectivity affects the extremal number of trees
• The number of edges in graphs with bounded clique number and circumference
• How connectivity affects the extremal number of trees (extended abstract)
• Generalized Turán problems for a matching and long cycles
• Stability results on the circumference of a graph

This page was built for publication: Cycles in 2-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705891)