论文标题
光谱图理论中的两个猜想涉及图特征值的线性组合
Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues
论文作者
论文摘要
我们证明了光谱极端图理论的两个猜想，涉及图特征值的线性组合。令$λ_1（g）$为图$ g $的邻接矩阵的最大特征值，而$ \ bar {g} $是$ g $的补充。 A nice conjecture states that the graph on $n$ vertices maximizing $λ_1(G) + λ_1(\bar{G})$ is the join of a clique and an independent set, with $\lfloor n/3\rfloor$ and $\lceil 2n/3\rceil$ (also $\lceil n/3\rceil$ and $\lfloor 2n/3 \ rfloor $如果$ n \ equiv 2 \ pmod {3} $）的顶点。我们使用分析方法解决了足够大的$ n $的猜想。我们的第二个结果涉及图$ g $的$ q $ -spread $ s_q（g）$，该$定义为$ g $的无标志性laplacian的最大特征值和最小特征值之间的差异。它是由Cvetković，Rowlinson和Simić猜想的，$ 2007 $，唯一的$ n $ n $ vertex连接图的最大$ q $ -spread的图是通过将吊坠边缘添加到$ k_ {n-1} $中形成的图。我们确认了这个猜想的足够大$ n $。
We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues. Let $λ_1(G)$ be the largest eigenvalue of the adjacency matrix of a graph $G$, and $\bar{G}$ be the complement of $G$. A nice conjecture states that the graph on $n$ vertices maximizing $λ_1(G) + λ_1(\bar{G})$ is the join of a clique and an independent set, with $\lfloor n/3\rfloor$ and $\lceil 2n/3\rceil$ (also $\lceil n/3\rceil$ and $\lfloor 2n/3\rfloor$ if $n \equiv 2 \pmod{3}$) vertices, respectively. We resolve this conjecture for sufficiently large $n$ using analytic methods. Our second result concerns the $Q$-spread $s_Q(G)$ of a graph $G$, which is defined as the difference between the largest eigenvalue and least eigenvalue of the signless Laplacian of $G$. It was conjectured by Cvetković, Rowlinson and Simić in $2007$ that the unique $n$-vertex connected graph of maximum $Q$-spread is the graph formed by adding a pendant edge to $K_{n-1}$. We confirm this conjecture for sufficiently large $n$.
