A Unique Characterization of Spectral Extrema for Friendship Graphs
A Unique Characterization of Spectral Extrema for Friendship Graphs
复制标题
DOI：
10.37236/11183
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
M. Zhai;Ruifang Liu;Jie Xue
中科院分区：
文献类型：
--
作者：
M. Zhai;Ruifang Liu;Jie Xue
Turán型问题是极图理论的核心问题之一。Erdas等人[J. Combin. Theory Ser. B 64（1995）89-100]给出了友谊图F_k$（n = 50 k ^2 $）的精确Turán数，并刻画了它的所有极图. Cioabbirth等人[Electron. J. Combin. 27（2020）Paper 22]首先将三角形移除引理引入到谱Turán型问题中，然后证明了$dac（n，F_k）\subseteq EX（n，F_k）$对于$n$足够大，其中$EX（n，F_k）$和$dac（n，F_k）$分别是具有最大尺寸和最大谱半径的$n$-顶点$F_k$-自由图族。本文证明了dac（n，F_k）族对于充分大的n是唯一确定的.我们的主要方法是在几乎正则图中寻找各种交替圈或闭迹。一些典型的光谱技术也被使用。这为其他谱极值问题的极值图的唯一性刻画提供了一种可能的方法。最后，我们提到了几个相关的建议。
Turán-type problem is one of central problems in extremal graph theory. Erdős et al. [J. Combin. Theory Ser. B 64 (1995) 89-100] obtained the exact Turán number of the friendship graph $F_k$ for $n\geq 50k^2$, and characterized all its extremal graphs. Cioabă et al. [Electron. J. Combin. 27 (2020) Paper 22] initially introduced Triangle Removal Lemma into a spectral Turán-type problem, then showed that $SPEX(n, F_k)\subseteq EX(n, F_k)$ for $n$ large enough, where $EX(n, F_k)$ and $SPEX(n, F_k)$ are the families of $n$-vertex $F_k$-free graphs with maximum size and maximum spectral radius, respectively. In this paper, the family $SPEX(n, F_k)$ is uniquely determined for sufficiently large $n$. Our key approach is to find various alternating cycles or closed trails in nearly regular graphs. Some typical spectral techniques are also used. This presents a probable way to characterize the uniqueness of extremal graphs for some of other spectral extremal problems. In the end, we mention several related conjectures.