Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size

DOI10.1016/J.DISC.2023.113591arXiv2206.09295OpenAlexW4383272313MaRDI QIDQ6080541

Shuchao Li, Wanting Sun, Wei Wei

Publication date: 4 October 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $mathcal{F}$ denote a set of graphs. A graph $G$ is said to be $mathcal{F}$-free if it does not contain any element of $mathcal{F}$ as a subgraph. The Tur'an number is the maximum possible number of edges in an $mathcal{F}$-free graph with $n$ vertices. It is well known that classical Tur'an type extremal problem aims to study the Tur'an number of fixed graphs. In 2010, Nikiforov cite{Nik2} proposed analogously a spectral Tur'an type problem which asks to determine the maximum spectral radius of an $mathcal{F}$-free graph with $n$ vertices. It attracts much attention and many such problems remained elusive open even after serious attempts, and so they are considered as one of the most intriguing problems in spectral extremal graph theory. It is interesting to consider another spectral Tur'an type problem which asks to determine the maximum spectral radius of an $mathcal{F}$-free graph with $m$ edges. Denote by $mathcal{G}(m,mathcal{F})$ the set of $mathcal{F}$-free graphs with $m$ edges having no isolated vertices. Each of the graphs among $mathcal{G}(m,mathcal{F})$ having the largest spectral radius is called a maximal graph. Let $ heta_{p,q,r}$ be a theta graph formed by connecting two distinct vertices with three independent paths of length $p,q$ and $r,$ respectively (length refers to the number of edges). In this paper, we firstly determine the unique maximal graph among $mathcal{G}(m, heta_{1,2,3})$ and $mathcal{G}(m, heta_{1,2,4}),$ respectively. Then we determine all the maximal graphs among $mathcal{G}(m,C_5)$ (resp. $mathcal{G}(m,C_6)$) excluding the book graph. These results extend some earlier results.

Full work available at URL: https://arxiv.org/abs/2206.09295

zbMATH Keywords

spectral radius\(\mathcal{F}\)-free graphsTurán-type extremal problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Spectra of graphs
• On a conjecture concerning spanning tree invariants and loop systems
• Spectral extrema of graphs: forbidden hexagon
• A contribution to the Zarankiewicz problem
• Walks and the spectral radius of graphs
• The spectral radius of graphs without paths and cycles of specified length
• The maximum spectral radius of \(C_4\)-free graphs of given order and size
• On a class of degenerate extremal graph problems
• On the spectral radius of (0,1)-matrices
• Spectral bounds for the clique and independence numbers of graphs
• Graphs without theta subgraphs
• On maximal entries in the principal eigenvector of graphs
• An extending result on spectral radius of bipartite graphs
• On the spectrum of an equitable quotient matrix and its application
• The extremal \(\alpha \)-index of graphs with no 4-cycle and 5-cycle
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• A conjecture on the spectral radius of graphs
• A spectral version of Mantel's theorem
• Spectral extrema for graphs: the Zarankiewicz problem
• Bounds on graph eigenvalues. II
• A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
• The maximum spectral radius of graphs of given size with forbidden subgraph
• Some new results in extremal graph theory
• Some Inequalities for the Largest Eigenvalue of a Graph
• Turán numbers of theta graphs
• Eigenvalues and triangles in graphs
• Merging the A-and Q-spectral theories
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size

Related Items (7)

Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ Spectral radius of graphs with given size and odd girth ⋮ A Brualdi-Hoffman-Turán problem on cycles ⋮ Maxima of the \(Q\)-index of leaf-free graphs with given size ⋮ Spectral extrema of graphs with fixed size: forbidden triangles and pentagons ⋮ Turán-type problems on \([a, b\)-factors of graphs, and beyond]

This page was built for publication: Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size