论文标题
在平面和外平面图的最大扩展上
On the maximum spread of planar and outerplanar graphs
论文作者
论文摘要
图$ g $的传播是$ g $的邻接矩阵的最大和最小特征值之间的差异。 Gotshall，O'Brien和Tait猜想，对于足够大的$ n $，$ n $ vertex Outerplanar图具有最大差异是通过将顶点连接到$ n-1 $顶点的路径获得的图形。在本文中，我们通过证明极端图是通过将顶点连接到$ \ lceil（2n-1）/3 \ rceil $ vertices和$ \ lfloor（n-2）/3 \ rfloor $隔离的pertices获得的路径来反驳这一猜想的。对于平面图，我们表明，达到最大差异的极端$ n $ vertex平面图是通过将两个非附在顶点连接到$ \ lceil（2n-2）/3 \ rceil $ debertices和$ \ lfloor（n-4）/3 \ rfloor $隔离的Vertices上获得的图形。
The spread of a graph $G$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $G$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $n$, the $n$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $\lceil (2n-1)/3\rceil$ vertices and $\lfloor(n-2)/3\rfloor$ isolated vertices. For planar graphs, we show that the extremal $n$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $\lceil(2n-2)/3\rceil$ vertices and $\lfloor(n-4)/3\rfloor$ isolated vertices.
