Spectral extremal graphs for intersecting cliques

DOI10.1016/J.LAA.2022.03.015MaRDI QIDQ2125679zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(25)

• The spectral radius of \(H_{2k}\)-free graphs
• The unique spectral extremal graph for intersecting cliques or intersecting odd cycles
• 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
• Decomposition of graphs into \((k,r)\)-fans and single edges
• Spectral extremal results on trees
• 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
• On a conjecture of spectral extremal problems
• Spectral Turán problems for intersecting even cycles
• 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
• scientific article; zbMATH DE number 5963787 (Why is no real title available?)

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)