Spectral extremal graphs for intersecting cliques

DOI10.1016/J.LAA.2022.03.015zbMATH Open1486.05178arXiv2108.03587OpenAlexW3197431628MaRDI QIDQ2125679FDOQ2125679

Authors: Yongtao Li, Zhenyu Ni, Michael Tait, Jing Wang, Dheer Noal Sunil Desai, Liying Kang 

Publication date: 14 April 2022

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

Abstract: The $(k,r)$-fan is the graph consisting of $k$ copies of the complete graph $K_r$ which intersect in a single vertex, and is denoted by $F_{k,r}$. ErdH{o}s, F"uredi, Gould and Gunderson [J. Combin. Theory Ser. B 64 (1995) 89--100] determined the maximum number of edges in an $n$-vertex graph that does not contain $F_{k,3}$ as a subgraph. Furthermore, Chen, Gould, Pfender and Wei [J. Combin. Theory Ser. B 89 (2003) 159--171] proved the analogous result on $F_{k,r}$ for the general case $rge3$.In this paper, we show that for sufficiently large $n$, the graphs of order $n$ that contain no copy of $F_{k,r}$ and attain the maximum spectral radius are also edge-extremal. That is, such graphs must have $mathrmex(n,F_{k,r})$ edges.

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

Recommendations

• Extremal graphs for intersecting triangles
• Spectral extremal graphs for disjoint cliques
• The spectral radius of graphs with no intersecting odd cycles
• On a conjecture of spectral extremal problems
• The signless Laplacian spectral radius of graphs with no intersecting triangles

zbMATH Keywords

spectral radiusextremal graphstability methodintersecting cliques

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Multilinear algebra, tensor calculus (15A69) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Some Inequalities for the Largest Eigenvalue of a Graph
• Title not available (Why is that?)
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Spectral radius and Hamiltonicity of graphs
• The spectral radius of graphs without paths and cycles of specified length
• Title not available (Why is that?)
• The history of degenerate (bipartite) extremal graph problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of linear graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extremal graphs for intersecting cliques
• Extremal graphs for intersecting triangles
• Intersection theorems for systems of sets
• On a problem of K. Zarankiewicz
• Degrees and matchings
• Bounds on graph eigenvalues. II
• Some new results in extremal graph theory
• A spectral Erdős-Stone-Bollobás theorem
• A contribution to the Zarankiewicz problem
• New asymptotics for bipartite Turán numbers
• An Upper Bound on Zarankiewicz' Problem
• Inverses of triangular matrices and bipartite graphs
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral saturation: inverting the spectral Turán theorem
• Eigenvalues of complete multipartite graphs
• Stability for large forbidden subgraphs
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Spectral radii of graphs with given chromatic number
• On spectral radius and energy of complete multipartite graphs
• The mathematics of Paul Erdős II
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• The maximum spectral radius of graphs without friendship subgraphs
• The spectral radius of graphs with no odd wheels

Cited In (25)

• Spectral extremal graphs for edge blow-up of star forests
• Maxima of the \(Q\)-index of non-bipartite graphs: forbidden short odd cycles
• Maxima of the \(Q\)-index: forbidden a Fan
• Spectral extremal results on trees
• Decomposition of graphs into \((k,r)\)-fans and single edges
• A Spectral Erdős-Sós Theorem
• The spectral even cycle problem
• On the spectral Turán problem of theta graphs
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• Refinement on Spectral Turán’s Theorem
• Spectral extremal graphs without intersecting triangles as a minor
• Turán-type problems on \([a, b]\)-factors of graphs, and beyond
• Spectral Turán problems for intersecting even cycles
• On a conjecture of spectral extremal problems
• Spectral extremal problem on disjoint color-critical graphs
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• Maxima of the \(Q\)-index of non-bipartite \(C_3\)-free graphs
• Spectral extremal graphs for the bowtie
• The maximum spectral radius of graphs of given size with forbidden subgraph
• A unique characterization of spectral extrema for friendship graphs
• Spectral extremal graphs for disjoint cliques
• Extremal graphs for the suspension of edge-critical graphs
• Title not available (Why is that?)
• The spectral radius of \(H_{2k}\)-free graphs
• The unique spectral extremal graph for intersecting cliques or intersecting odd cycles

This page was built for publication: Spectral extremal graphs for intersecting cliques

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