Extensions on spectral extrema of _1,2,5-free graphs with given size

DOI10.1016/J.LAA.2025.04.010MaRDI QIDQ6985246zbMATH OpenFDO

Authors Chang Liu, Jianping Li

Publication date 13 May 2025

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.LAA.2025.04.010

zbMATH Keywords

cyclespectral radiustheta graphTurán-type extremal problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

Let \(\mathcal{F}\) be a set of graphs. A graph \(G\) is called \(\mathcal{F}\)-free if it does not contain any subgraph isomorphic to a graph in \(\mathcal{F}\). In 1985, \textit{R. A. Brualdi} and \textit{A. J. Hoffman} [Linear Algebra Appl. 65, 133--146 (1985; Zbl 0563.15012)] posed an interesting problem: What is the maximal spectral radius of an \(\mathcal{F}\)-free graph with a given size \(m\)? The above problem is referred to as the Brualdi-Hoffman-Turán problem. This paper addresses this problem for \(\theta_{1,2,5}\)-free graphs. The theta graph \(\theta_{p,q,r}\) is a graph consisting of three internally disjoint paths of lengths \(p\), \(q\), and \(r\), sharing the same pair of endpoints. In this study, the authors present a new method to characterize the graphs with the maximum spectral radius among all \(\theta_{1,2,5}\)-free graphs for \(m \geq 39\), where \(m \equiv 1\pmod 3\) or \(m \equiv 2\pmod 3\).

Cites work

• A Brualdi-Hoffman-Turán problem on cycles
• A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
• A spectral version of Mantel's theorem
• An introduction to the theory of graph spectra
• Bounds on graph eigenvalues. II
• Cauchy's Interlace Theorem for Eigenvalues of Hermitian Matrices
• Connected graphs without long paths
• Eigenvalues and triangles in graphs
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
• scientific article; zbMATH DE number 3372065 (Why is no real title available?)
• More spectral bounds on the clique and independence numbers
• On the maximal index of graphs with a prescribed number of edges
• On the spectral radius of (0,1)-matrices
• Some Inequalities for the Largest Eigenvalue of a Graph
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• Spectral extrema of graphs: forbidden hexagon
• Spectral extremal graphs for intersecting cliques
• Spectral extremal results with forbidding linear forests
• Spectral radius of graphs forbidden C₇ or C₆^
• Spectral radius of graphs of given size with forbidden subgraphs
• Spectral radius of graphs with given size and odd girth
• The maximum spectral radius of C₄-free graphs of given order and size
• The maximum spectral radius of graphs of given size with forbidden subgraph
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• The spectral radius of graphs without paths and cycles of specified length
• Three conjectures in extremal spectral graph theory
• Upper bounds of spectral radius of symmetric matrices and graphs
• Walks and the spectral radius of graphs

This page was built for publication: Extensions on spectral extrema of \(\theta_{1,2,5}\)-free graphs with given size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6985246)