论文标题
Bowtie的光谱极端图
Spectral extremal graphs for the bowtie
论文作者
论文摘要
让$ f_k $是通过共享一个普通顶点从$ k $三角形获得的（友谊）图。 $ f_k $ - 达到最大光谱半径的订单$ n $的图形首先以Cioabă，Feng，Tait和Zhang [Electron。 J. Combin。 27（4）（2020）]，后来由Zhai，Liu和Xue [Electron。 J. Combin。 29（3）（2022）]条件是$ n $足够大。在本文中，如果$ k = 2 $，我们将摆脱$ n $的条件。图$ F_2 $也称为Bowtie。我们表明，唯一的$ n $ vertex $ f_2 $ - 免费的光谱极端图是平衡的完整二分化图，如果$ n \ ge 7 $，并且条件$ n \ ge 7 $紧密。我们的结果是对Erdős，Füredi，Gould和Gunderson定理的光谱概括[J.组合。理论ser。 b 64（1995）]，它指出$ \ mathrm {ex}（n，f_2）= \ left \ lfloor {n^2}/{4} \ right \ rfloor +1 $。此外，我们研究具有给定数量的边缘的$ f_k $ - 免费图形的光谱极端问题。特别是，我们表明唯一的$ M $ -EDGE $ f_2 $ -free Spectral极限图是$ k_2 $的连接，具有独立的$ \ frac {m-1} {2} $ vertices，如果$ m \ ge 8 $，并且条件$ m \ ge 8 $很紧。
Let $F_k$ be the (friendship) graph obtained from $k$ triangles by sharing a common vertex. The $F_k$-free graphs of order $n$ which attain the maximal spectral radius was firstly characterized by Cioabă, Feng, Tait and Zhang [Electron. J. Combin. 27 (4) (2020)], and later uniquely determined by Zhai, Liu and Xue [Electron. J. Combin. 29 (3) (2022)] under the condition that $n$ is sufficiently large. In this paper, we get rid of the condition on $n$ being sufficiently large if $k=2$. The graph $F_2$ is also known as the bowtie. We show that the unique $n$-vertex $F_2$-free spectral extremal graph is the balanced complete bipartite graph adding an edge in the vertex part with smaller size if $n\ge 7$, and the condition $n\ge 7$ is tight. Our result is a spectral generalization of a theorem of Erdős, Füredi, Gould and Gunderson [J. Combin. Theory Ser. B 64 (1995)], which states that $\mathrm{ex}(n,F_2)=\left\lfloor {n^2}/{4} \right\rfloor +1$. Moreover, we study the spectral extremal problem for $F_k$-free graphs with given number of edges. In particular, we show that the unique $m$-edge $F_2$-free spectral extremal graph is the join of $K_2$ with an independent set of $\frac{m-1}{2}$ vertices if $m\ge 8$, and the condition $m\ge 8$ is tight.
