Spectral extrema of graphs with bounded clique number and matching number

DOI10.1016/J.LAA.2023.03.026MaRDI QIDQ6046080zbMATH OpenFDO

Authors Hongyu Wang, Xinmin Hou, Yue Ma

Publication date 15 May 2023

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

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

zbMATH Keywords

adjacency matrixspectral radiusTuran graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a set of graphs $mathcalF$, let $ex(n,mathcalF)$ and $spex(n,mathcalF)$ denote the maximum number of edges and the maximum spectral radius of an $n$-vertex $mathcalF$-free graph, respectively. Nikiforov ({em LAA}, 2007) gave the spectral version of the Tur'an Theorem by showing that $spex(n,K_{k+1})=lambda(T_k(n))$, where $T_k(n)$ is the $k$-partite Tur'an graph on $n$ vertices. In the same year, Feng, Yu and Zhang ({em LAA}) determined the exact value of $spex(n,M_{s+1})$, where $M_{s+1}$ is a matching with $s+1$ edges. Recently, Alon and Frankl~(arXiv2210.15076) gave the exact value of $ex(n,K_{k+1},M_{s+1})$. In this article, we give the spectral version of the result of Alon and Frankl by determining the exact value of $spex(n,K_{k+1},M_{s+1})$ when $n$ is large.

Review text

In this paper, the authors prove that the extremal graph having the maximal spectral radius among the graphs on \(n\) vertices having clique number at most \(k\) and matching number at most \(s\) is the complete \(k\)-partite graph with one partition set of size \(n-s\) and the others having sizes as equal as possible. This result is a spectral version of the analogous result on the number of edges by \textit{N. Alon} and \textit{P. Frankl} [``Turán graphs with bounded matching number, Preprint, \url{arXiv:2210.15076}]. The main technique of the proof is the Perron-Frobenius theorem.

Recommendations

• Spectral radius of graphs with given matching number
• Spectral extremal graphs for disjoint cliques
• Matchings in graphs from the spectral radius
• Spectral radius and clique partitions of graphs
• The maximum spectral radius of \(t\)-connected graphs with bounded matching number

Cites work

• Bounds on graph eigenvalues. II
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• On maximal paths and circuits of graphs
• On the spectrum of a complete multipartite graph
• Paths, Trees, and Flowers
• Some new results in extremal graph theory
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• Spectral extremal graphs for disjoint cliques
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• Spectral radius of graphs with given matching number
• Spectral radius, edge-disjoint cycles and cycles of the same length
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• The spectral radius of graphs with no odd wheels
• The spectral radius of graphs without long cycles
• The spectral radius of graphs without paths and cycles of specified length
• The spectral radius of graphs without trees of diameter at most four

Cited in

(19)

• Cliques and the spectral radius
• Complete subgraphs in connected graphs and its application to spectral moment
• On a conjecture of spectral extremal problems
• Spectral extremal graphs for disjoint cliques
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• Spectral proofs of maximality of some Seidel matrices
• An extremal problem on Q-spectral radii of graphs with given size and matching number
• Spectral extremal graphs for the bowtie
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• Spectral extrema of graphs: forbidden linear forests and non-bipartite graphs
• Spectral extrema of graphs: forbidden cliques and star forests
• A spectral generalized Alon-Frankl theorem
• The number of edges in graphs with bounded clique number and circumference
• Spectral extremal problems for graphs with bounded clique number
• Some stability results for spectral extremal problems of graphs with bounded matching number
• Turán numbers of cycles plus a general graph
• Many cliques in graphs with bounded matching number and circumference
• Eigenvalues and factors: a survey

This page was built for publication: Spectral extrema of graphs with bounded clique number and matching number

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