Stability results on the circumference of a graph

DOI10.1007/S00493-019-3843-4zbMATH Open1449.05163arXiv1708.00704OpenAlexW3098406359WikidataQ126349608 ScholiaQ126349608MaRDI QIDQ783243FDOQ783243

Jie Ma, Bo Ning

Publication date: 11 August 2020

Published in: Combinatorica (Search for Journal in Brave)

Abstract: In this paper, we extend and refine previous Tur'an-type results on graphs with a given circumference. Let $W_{n,k,c}$ be the graph obtained from a clique $K_{c-k+1}$ by adding $n-(c-k+1)$ isolated vertices each joined to the same $k$ vertices of the clique, and let $f(n,k,c)=e(W_{n,k,c})$. Improving a celebrated theorem of ErdH{o}s and Gallai, Kopylov proved that for $c<n$, any 2-connected graph $G$ on $n$ vertices with circumference $c$ has at most $maxf(n,2,c),f(n,lfloorfracc2floor,c)$ edges. Recently, F"uredi et al. proved a stability version of Kopylov's theorem. Their main result states that if $G$ is a 2-connected graph on $n$ vertices with circumference $c$ such that $10leqc<n$ and $e(G)>maxf(n,3,c),f(n,lfloorfracc2floor-1,c)$, then either $G$ is a subgraph of $W_{n,2,c}$ or $W_{n,lfloorfracc2floor,c}$, or $c$ is odd and $G$ is a subgraph of a member of two well-characterized families which we define as $mathcal{X}_{n,c}$ and $mathcal{Y}_{n,c}$. We prove that if $G$ is a 2-connected graph on $n$ vertices with minimum degree at least $k$ and circumference $c$ such that $10leqc<n$ and $e(G)>maxf(n,k+1,c),f(n,lfloorfracc2floor-1,c)$, then one of the following holds: (i) $G$ is a subgraph of $W_{n,k,c}$ or $W_{n,lfloorfracc2floor,c}$, (ii) $k=2$, $c$ is odd, and $G$ is a subgraph of a member of $mathcal{X}_{n,c}cupmathcal{Y}_{n,c}$, or (iii) $kgeq3$ and $G$ is a subgraph of the union of a clique $K_{c-k+1}$ and some cliques $K_{k+1}$'s, where any two cliques share the same two vertices. This provides a unified generalization of the above result of F"uredi et al. as well as a recent result of Li et al. and independently, of F"uredi et al. on non-Hamiltonian graphs. Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.

Full work available at URL: https://arxiv.org/abs/1708.00704

Recommendations

• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Stability of Woodall's theorem and spectral conditions for large cycles
• scientific article
• A short proof of Fan's theorem
• A new short proof of fan theorem
• A note on covering the edges of a graph with bonds
• A short proof of a theorem about the circumference of a graph
• An Upper Bound on the Number of Edges of a 2-Connected Graph
• Publication:5753979
• scientific article

zbMATH Keywords

cliqueclosure operationWoodall's conjectureHamiltonian graph2-connected graphedge-switching techniquegraph circumference

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40) Extremal combinatorics (05D99)

Cites Work

• Title not available (Why is that?)
• On Hamilton's ideals
• Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles
• On maximal paths and circuits of graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• On a closure concept in claw-free graphs
• Path Ramsey numbers in multicolorings
• Title not available (Why is that?)
• Maximal circuits of graphs. I
• Some Theorems on Abstract Graphs
• Large cycles in graphs
• On maximal circuits in directed graphs
• A method in graph theory
• Stability in the Erdős-Gallai theorems on cycles and paths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Long cycles and the codiameter of a graph. I
• Arc coverings of graphs
• Cycles in 2-connected graphs
• Stability in the Erdős-Gallai theorem on cycles and paths. II
• A stability version for a theorem of Erdős on nonhamiltonian graphs
• Extensions of a theorem of Erdős on nonhamiltonian graphs

Cited In (14)

• A stability result of the Pósa lemma
• Exact bipartite Turán numbers of large even cycles
• Stability of Woodall's theorem and spectral conditions for large cycles
• A note on the stability results of the number of cliques in graphs with given matching number
• Minimum number of edges guaranteeing the existence of a \(K_{1, t}\)-factor in a graph
• Further results on the generalized Turán number of spanning linear forests
• Non-Hamiltonian graphs with large minimum degree
• Extremal graphs for the odd prism
• The maximum number of cliques in graphs with prescribed order, circumference and minimum degree
• Maximizing the number of cliques in graphs with given matching number
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• Stability of Reeb Graphs of Closed Curves
• Stability version of Dirac's theorem and its applications for generalized Turán problems

This page was built for publication: Stability results on the circumference of a graph

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