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

spectral radiusadjacency matrixTuran graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) 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.

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

• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• Bounds on graph eigenvalues. II
• 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

(10)

• Spectral proofs of maximality of some Seidel matrices
• Cliques and the spectral radius
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
• Spectral extremal graphs for disjoint cliques
• An extremal problem on Q-spectral radii of graphs with given size and matching number
• Complete subgraphs in connected graphs and its application to spectral moment
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• Spectral extremal graphs for the bowtie
• On a conjecture of spectral extremal problems

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)