论文标题
旋塞图的韧性
The Toughness of Kneser Graphs
论文作者
论文摘要
图$ g $的\ textIt {arthness} $ t（g）$是其连接性的衡量，与哈密顿密切相关。布鲁维尔证明了在任何连接的$ \ ell $ regular-graph的韧性上的下限$ t（g）> \ ell /λ-2 $，其中$λ$是邻接矩阵的最大非平凡特征值。他猜想该下限可以提高到$ \ ell /λ1$，并且该猜想仍然开放。布鲁维尔还观察到，许多图的家族（特别是那些以霍夫曼比率达到独立数量的平等的家族）具有韧性恰好$ \ ell /λ$。 Cioabă和Wong证实了Brouwer对几个图形系列的观察，包括Kneser Graphs $ K（N，2）$及其补充，除了Petersen Graph $ k（5,2）$。在本文中，我们扩展了这些结果并确定$ k \ in \ in \ {3,4 \} $和$ n \ geq 2k+1 $以及$ k \ geq 5 $和足够大的$ n $（在$ k $中）时，确定了$ k（n，k）$的韧性。在所有这些情况下，韧性都是通过最大独立集的补充来实现的，我们猜测，对于任何$ k \ geq 5 $和$ n \ geq 2k+1 $ $的情况都是这种情况。
The \textit{toughness} $t(G)$ of a graph $G$ is a measure of its connectivity that is closely related to Hamiltonicity. Brouwer proved the lower bound $t(G) > \ell / λ- 2$ on the toughness of any connected $\ell$-regular graph, where $ λ$ is the largest nontrivial eigenvalue of the adjacency matrix. He conjectured that this lower bound can be improved to $\ell / λ-1$ and this conjecture is still open. Brouwer also observed that many families of graphs (in particular, those achieving equality in the Hoffman ratio bound for the independence number) have toughness exactly $\ell / λ$. Cioabă and Wong confirmed Brouwer's observation for several families of graphs, including Kneser graphs $K(n,2)$ and their complements, with the exception of the Petersen graph $K(5,2)$. In this paper, we extend these results and determine the toughness of Kneser graphs $K(n,k)$ when $k\in \{3,4\}$ and $n\geq 2k+1$ as well as for $k\geq 5$ and sufficiently large $n$ (in terms of $k$). In all these cases, the toughness is attained by the complement of a maximum independent set and we conjecture that this is the case for any $k\geq 5$ and $n\geq 2k+1$.
