12 papers
Positive discrepancy of graphs far from Turán graphs
Leyou Xu, Bo Zhou
We prove that, for every $\eps>0$, any -vertex graph that needs at least $\eps n^2$ edge changes to become a Turán graph has positive discrepancy at least $c_\eps n^{5/4}$. Cons…
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…
Answers to Gould's question concerning the existence of chorded cycles
Leyou Xu, Bo Zhou
Answers are offered to the Gould's question to find spectral sufficient conditions for a graph to have a chorded cycle via signless Laplacian spectral radius. The conditions are ti…
Distribution of signless Laplacian eigenvalues and graph invariants
Leyou Xu, Bo Zhou
For a simple graph on vertices, any of its signless Laplacian eigenvalues is in the interval . In this paper, we give relationships between the number of signless La…
Link residual closeness of graphs with fixed parameters
Leyou Xu, Chengli Li, Bo Zhou
Link residual closeness is a newly proposed measure for network vulnerability. In this model, vertices are perfectly reliable and the links fail independently of each other. It mea…
Toughness and existence of -factors
Leyou Xu, Bo Zhou
A graph is -tough if the deletion of any set of, say, vertices from the graph leaves a graph with at most components. In 1973, Chvátal suggested the problem of…
The Alon-Tarsi number of -minor-free graphs
Leyou Xu, Bo Zhou
The well known Wagner's theorem states that a graph is a planar graph if and only if it is -minor-free and -minor-free. Denote by the Alon-Tarsi number of a g…