Spectral extrema of graphs with bounded clique number and matching number

DOI10.1016/J.LAA.2023.03.026zbMATH Open1519.05165arXiv2302.04695MaRDI QIDQ6046080FDOQ6046080

Authors: Hongyu Wang, Xinmin Hou, Yue Ma 

Publication date: 15 May 2023

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

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.

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

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

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)

Cites Work

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

Cited In (10)

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

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)