Stability of Woodall's theorem and spectral conditions for large cycles (Q2692178): Difference between revisions
From MaRDI portal
Latest revision as of 19:05, 31 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stability of Woodall's theorem and spectral conditions for large cycles |
scientific article |
Statements
Stability of Woodall's theorem and spectral conditions for large cycles (English)
0 references
21 March 2023
0 references
Summary: \textit{P. Erdős} [in: Combinat. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 97--109 (1971; Zbl 0221.05051)] asked how many edges are needed in a graph on \(n\) vertices, to ensure the existence of a cycle of length exactly \(n-k\). In this paper, we consider the spectral analog of Erdős' problem. Indeed, the problem of determining tight spectral radius conditions for cycles of length \(\ell\) in a graph of order \(n\) for each \(\ell \in[3,n]\) seems very difficult. We determine tight spectral radius conditions for \(C_{\ell}\) where \(\ell\) belongs to an interval of the form \([n-\Theta(\sqrt{n}),n]\). As a main tool, we prove a stability result of a theorem due to \textit{D. R. Woodall} [Proc. Lond. Math. Soc. (3) 24, 739--755 (1972; Zbl 0233.05117)], which states that for a graph \(G\) of order \(n\geqslant 2k+3\) where \(k\geqslant 0\) is an integer, if \(e(G)>\binom{n-k-1}{2}+\binom{k+2}{2}\) then \(G\) contains a \(C_{\ell}\) for each \(\ell\in [3,n-k]\). We prove a tight spectral condition for the circumference of a \(2\)-connected graph with a given minimum degree, of which the main tool is a stability version of a conjecture of \textit{D. R. Woodall} [Acta Math. Acad. Sci. Hung. 28, 77--80 (1976; Zbl 0337.05128)] on circumference of a \(2\)-connected graph with a given minimum degree proved by \textit{J. Ma} and \textit{B. Ning} [Combinatorica 40, No. 1, 105--147 (2020; Zbl 1449.05163)]. We also give a brief survey on this area and point out where we are and our predicament.
0 references
graph circumference
0 references
clique
0 references
closure operation
0 references
edge-switching technique
0 references
Hamiltonian graph
0 references
Woodall's conjecture
0 references
2-connected graph
0 references
0 references