外平面图和平面图上的谱极值问题

Spectral extremal problems on outerplanar and planar graphs

摘要 Abstract

设$\emph{spex}_{\mathcal{OP}}(n,F)$和$\emph{spex}_{\mathcal{P}}(n,F)$分别为所有顶点数为$n$且不含子图$F$的外平面图和平面图的最大谱半径。定义$tC_l$为$t$个互不相邻的$l$-圈,$B_{tl}$为通过一个公共顶点连接$t$个互不相交的$l$-圈所得到的图(即$tC_l$中的所有圈共享一个顶点),$(t+1)K_{2}$为$t+1$个互不相连的$K_2$的不交并。20世纪90年代,Cvetković和Rowlinson猜想,$K_1 \vee P_{n-1}$在外平面图中最大化谱半径,而Boots和Royle(独立地,Cao和Vince)则猜想$K_2 \vee P_{n-2}$在平面图中最大化谱半径。Tait和Tobin [J. Combin. Theory Ser. B, 2017]确定了这一猜想成立的关键结构。最近,Fang等人[J. Graph Theory, 2024]利用这一关键结构刻画了平面图中$\emph{spex}_{\mathcal{P}}(n,tC_l)$对应的极值图。本文首先关注外平面图,并采用类似方法描述了与$\emph{spex}_{\mathcal{OP}}(n,F)$相关的连通极值图的关键结构,其中$F$包含于$K_1 \vee P_{n-1}$但不包含于$K_{1} \vee ((t-1)K_2\cup(n-2t+1)K_1)$。基于此结构,我们确定了所有$t\geq1$、$l\geq3$以及足够大的$n$时的$\emph{spex}_{\mathcal{OP}}(n,B_{tl})$和$\emph{spex}_{\mathcal{OP}}(n,(t+1)K_{2})$及其唯一的极值图。此外,我们将结果进一步推广到平面图,刻画了所有$t\geq3$、$l\geq3$以及足够大的$n$时$\emph{spex}_{\mathcal{P}}(n,B_{tl})$对应的唯一极值图。

Let $\emph{spex}_{\mathcal{OP}}(n,F)$ and $\emph{spex}_{\mathcal{P}}(n,F)$ be the maximum spectral radius over all $n$-vertex $F$-free outerplanar graphs and planar graphs, respectively. Define $tC_l$ as $t$ vertex-disjoint $l$-cycles, $B_{tl}$ as the graph obtained by sharing a common vertex among $t$ edge-disjoint $l$-cycles %$B_{tl}$ as the graph obtained by connecting all cycles in $tC_l$ at a single vertex, and $(t+1)K_{2}$ as the disjoint union of $t+1$ copies of $K_2$. In the 1990s, Cvetkovi\'c and Rowlinson conjectured $K_1 \vee P_{n-1}$ maximizes spectral radius in outerplanar graphs on $n$ vertices, while Boots and Royle (independently, Cao and Vince) conjectured $K_2 \vee P_{n-2} $ does so in planar graphs. Tait and Tobin [J. Combin. Theory Ser. B, 2017] determined the fundamental structure as the key to confirming these two conjectures for sufficiently large $n.$ Recently, Fang et al. [J. Graph Theory, 2024] characterized the extremal graph with $\emph{spex}_{\mathcal{P}}(n,tC_l)$ in planar graphs by using this key. In this paper, we first focus on outerplanar graphs and adopt a similar approach to describe the key structure of the connected extremal graph with $\emph{spex}_{\mathcal{OP}}(n,F)$, where $F$ is contained in $K_1 \vee P_{n-1}$ but not in $K_{1} \vee ((t-1)K_2\cup(n-2t+1)K_1)$. Based on this structure, we determine $\emph{spex}_{\mathcal{OP}}(n,B_{tl})$ and $\emph{spex}_{\mathcal{OP}}(n,(t+1)K_{2})$ along with their unique extremal graphs for all $t\geq1$, $l\geq3$ and large $n$. Moreover, we further extend the results to planar graphs, characterizing the unique extremal graph with $\emph{spex}_{\mathcal{P}}(n,B_{tl})$ for all $t\geq3$, $l\geq3$ and large $n$.

外平面图和平面图上的谱极值问题 - arXiv