TY - UNPB
T1 - Graph Toughness from Laplacian Eigenvalues
AU - Gu, Xiaofeng
AU - Haemers, Willem H.
PY - 2021/4/8
Y1 - 2021/4/8
N2 - The toughness $t(G)$ of a graph $G=(V,E)$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum is taken over all $S\subset V$ such that $G-S$ is disconnected, where $c(G-S)$ denotes the number of components of $G-S$. We present two tight lower bounds for $t(G)$ in terms of the Laplacian eigenvalues and provide strong support for a conjecture for a better bound which, if true, implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author. As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained, which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.
AB - The toughness $t(G)$ of a graph $G=(V,E)$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum is taken over all $S\subset V$ such that $G-S$ is disconnected, where $c(G-S)$ denotes the number of components of $G-S$. We present two tight lower bounds for $t(G)$ in terms of the Laplacian eigenvalues and provide strong support for a conjecture for a better bound which, if true, implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author. As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained, which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.
KW - math.CO
KW - 05C42, 05C50, 05C70, 05C45
M3 - Working paper
T3 - arXiv
BT - Graph Toughness from Laplacian Eigenvalues
PB - Cornell University Library
CY - Ithaca
ER -