Extremal spectral results of planar graphs without vertex-disjoint cycles

DOI10.1002/JGT.23084arXiv2304.06942MaRDI QIDQ6433062

Yongtang Shi, Longfei Fang, Huiqiu Lin

Publication date: 14 April 2023

Abstract: Given a planar graph family $mathcalF$, let ${mex}_{mathcalP}(n,mathcalF)$ and ${mspex}_{mathcalP}(n,mathcalF)$ be the maximum size and maximum spectral radius over all $n$-vertex $mathcalF$-free planar graphs, respectively. Let $t{C}_k$ be the disjoint union of $t$ copies of $k$-cycles, and $tmathcalC$ be the family of $t$ vertex-disjoint cycles without length restriction. Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B 126 (2017) 137--161] determined that $K_2+P_{n-2}$ is the extremal spectral graph among all planar graphs with sufficiently large order $n$, which implies the extreme graphs of $spe{x}_{mathcalP}(n,t{C}_{ell})$ and $spe{x}_{mathcalP}(n,tmathcalC)$ for $tgeq3$ are $K_2+P_{n-2}$. In this paper, we first determine $spe{x}_{mathcalP}(n,t{C}_{ell})$ and $spe{x}_{mathcalP}(n,tmathcalC)$ and characterize the unique extremal graph for $1leqtleq2$, $ellgeq3$ and sufficiently large $n$. Secondly, we obtain the exact values of ${mex}_{mathcalP}(n,2C_4)$ and ${mex}_{mathcalP}(n,2mathcalC)$, which answers a conjecture of Li [Planar Tur'an number of disjoint union of $C_3$ and $C_4$, arxiv:2212.12751v1 (2022)]. These present a new exploration of approaches and tools to investigate extremal problems of planar graphs.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Related Items (1)

Spectral extrema of 1-planar graphs

This page was built for publication: Extremal spectral results of planar graphs without vertex-disjoint cycles