5 papers · 1 filter
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…