10 papers · 1 filter
Large Complete Minors from a Cheeger Condition
Chengli Li, Leyou Xu, Bo Zhou
Let be a graph on vertices, and let be the number of edges with exactly one endpoint in . The Cheeger constant and the restricted Cheeger consta…
Proving a conjecture concerning chromatic number, size and least eigenvalue
Leyou Xu, Bo Zhou
Let be a simple nonempty graph with size , chromatic number , and least eigenvalue . We prove that \[ χ(χ-1) \le (m+1-λ^2)+\sqrt{(m+1-λ^2)^2-4(λ^2-1)(λ^2-m)} \] with e…
The number of cycles of a given length in dense hamiltonian graphs: proving Hilton's conjecture
Chengli Li, Leyou Xu, Bo Zhou
A classical theorem of Sheehan in 1977 states that every hamiltonian graph of order satisfying contains at least two cycles…
On -connected vertex-pancyclic graphs without pancyclic edges
Leyou Xu, Bo Zhou
An edge of a graph of order is pancyclic if it lies in a cycle of every length . A graph of order is vertex-pancyclic if every vertex lies in a cycle of every l…
Girth and Laplacian eigenvalue distribution
Leyou Xu, Bo Zhou
Let be a connected graph of order with girth . For , let be the number of Laplacian eigenvalues (counting multiplicities) of tha…
Spectral conditions implying the existence of doubly chorded cycles without or with constraints
Leyou Xu, Bo Zhou
What spectral conditions imply a graph contains a chorded cycle? This question was asked by R.J. Gould in 2022. We answer two modified versions of Gould's question by giving tight…