论文标题
布鲁维尔韧性的证明
A proof of Brouwer's toughness conjecture
论文作者
论文摘要
连接的图$ g $的韧性$ t（g）$定义为$ t（g）= \ min \ {\ frac {| s | |} {c（g-s）} \} $，其中将最低限制在所有适当的子集对$ s \ subset v（g）$ c（g）$ c（g-s）$ c（g-s）$ c（g s）$ s $ c（g）$ c（g）中$ c（g）$ c（g）$ c（g）令$λ$表示图的邻接矩阵的第二大绝对特征值。对于任何连接的$ d $ - 台式$ g $，Alon已证明$ t（g）> \ frac {1} {3}（\ frac {d^2} {dλ+λ^2} -1）$强烈的猜想在繁殖时。 Brouwer独立地发现了任何连接的$ d $ regragh Graph $ g $的更好界限$ t（g）> \ frac {d}λ-2$，而他还猜想下界可以将下限提高到$ t（g）\ ge \ ge \ frac {d}λ-λ-1$。我们确认这个猜想。
The toughness $t(G)$ of a connected graph $G$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum is taken over all proper subsets $S\subset V(G)$ such that $c(G-S)>1$, where $c(G-S)$ denotes the number of components of $G-S$. Let $λ$ denote the second largest absolute eigenvalue of the adjacency matrix of a graph. For any connected $d$-regular graph $G$, it has been shown by Alon that $t(G)>\frac{1}{3}(\frac{d^2}{dλ+λ^2}-1)$, through which, Alon was able to show that for every $t$ and $g$ there are $t$-tough graphs of girth strictly greater than $g$, and thus disproved in a strong sense a conjecture of Chvátal on pancyclicity. Brouwer independently discovered a better bound $t(G)>\frac{d}λ-2$ for any connected $d$-regular graph $G$, while he also conjectured that the lower bound can be improved to $t(G)\ge \frac{d}λ - 1$. We confirm this conjecture.
