论文标题
可从多项式型方法获得的3独立数的最佳结合
The optimal bound on the 3-independence number obtainable from a polynomial-type method
论文作者
论文摘要
连接图中的$ k $独立的集合是一组顶点，使得集中的任何两个顶点在图中的距离大于$ k $。图形的$ k $独立数，表示为$α_k$，是图中最大的$ k $独立设置的大小。最近的结果利用了取决于图的频谱以绑定$ k $独立的数字的多项式。它们针对$ k = 1,2 $的情况进行了优化。有些多项式可以为一般$ k $带来良好（有时）的最佳结果，包括案例$ k = 3 $。在本文中，我们提供了最佳的界限，可以通过选择案例$ k = 3 $的多项式来获得，并将其应用于包括Hamming图的众所周知的图形家庭。
A $k$-independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than $k$ in the graph. The $k$-independence number of a graph, denoted $α_k$, is the size of a largest $k$-independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the $k$-independence number. They are optimized for the cases $k=1,2$. There are polynomials that give good (and sometimes) optimal results for general $k$, including case $k=3$. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case $k=3$ and apply this bound to well-known families of graphs including the Hamming graph.
