Eigenvalues and triangles in graphs

DOI10.1017/S0963548320000462zbMATH Open1466.05121arXiv1910.12474OpenAlexW3090797620MaRDI QIDQ4993261FDOQ4993261

Authors: Huiqiu Lin, Bo Ning, Baoyindureng Wu 

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Bollob'as and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $lambd{a}_1^2(G)+lambd{a}_2^2(G)leqfracr-1rcdot2m$, where $lambd{a}_1(G)$ and $lambd{a}_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to ErdH{o}s and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $lambd{a}_1(G)geqsqrtm-1$ and $Geq{C}_{5}cup(n-5)K_1$; and (2) $lambd{a}_1(G)geqlambd{a}_1(S(K_{lfloorfracn-12floor,lceilfracn-12ceil}))$ and $GeqS(K_{lfloorfracn-12floor,lceilfracn-12ceil})$, where $S(K_{lfloorfracn-12floor,lceilfracn-12ceil})$ is obtained from $K_{lfloorfracn-12floor,lceilfracn-12ceil}$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.

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

Recommendations

• Eigenvalues and forbidden subgraphs. I.
• Eigenvalue multiplicity in triangle-free graphs
• Counting substructures and eigenvalues. I: Triangles
• Note on the sum of the smallest and largest eigenvalues of a triangle-free graph
• The Spectrum of Triangle-Free Graphs

zbMATH Keywords

adjacency matrixspectral extremal graph theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Graph theory
• Eigenvalues and expanders
• More spectral bounds on the clique and independence numbers
• A sharp upper bound of the spectral radius of graphs
• Hamilton cycles and eigenvalues of graphs
• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
• Some Inequalities for the Largest Eigenvalue of a Graph
• Title not available (Why is that?)
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Matrix theory
• Matchings in regular graphs from eigenvalues
• Bipartite subgraphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Bipartite graphs with at most six non-zero eigenvalues
• Some new results in extremal graph theory
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• Proof of a conjectured lower bound on the chromatic number of a graph
• Lower bounds for the clique and the chromatic numbers of a graph
• Spectral radius and \(k\)-connectedness of a graph
• Title not available (Why is that?)
• Cliques and the spectral radius
• Walks and the spectral radius of graphs
• Spectral bounds for the clique and independence numbers of graphs
• Title not available (Why is that?)
• Eigenvalues and perfect matchings
• Regular graphs, eigenvalues and regular factors
• Bounds of eigenvalues of a graph
• On the largest eigenvalue of non-regular graphs
• The maximum spectral radius of \(C_4\)-free graphs of given order and size
• Linear Separation of Dominating Sets in Graphs
• A lower bound for the spectral radius of graphs with fixed diameter
• Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph
• Three conjectures in extremal spectral graph theory

Cited In (63)

• The Spectrum of Triangle-Free Graphs
• Adjacency eigenvalues of graphs without short odd cycles
• Lower bounds on the number of triangles in a graph
• Maxima of the \(Q\)-index of non-bipartite graphs: forbidden short odd cycles
• Two conjectured strengthenings of Turán's theorem
• On the first two eigenvalues of regular graphs
• Maximum degree and spectral radius of graphs in terms of size
• An algorithm for constructing graphs with given eigenvalues and angles
• The index of signed graphs with forbidden subgraphs
• Maximizing the signless Laplacian spectral radius of minimally 3-connected graphs with given size
• Signless Laplacian spectral radius of graphs without short cycles or long cycles
• Eigenvalues and forbidden subgraphs. I.
• Sharp upper bounds on the \(Q\)-index of (minimally) 2-connected graphs with given size
• Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
• Note on the sum of the smallest and largest eigenvalues of a triangle-free graph
• Refinement on Spectral Turán’s Theorem
• The general spectral radii of (multicone-)graphs with prescribed degree sequence
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Maximizing the degree powers of graphs with fixed size
• Some extremal problems on \(A_\alpha \)-spectral radius of graphs with given size
• Characterizing \(\mathcal{P}_{\geqslant 2}\)-factor deleted graphs with respect to the size or the spectral radius
• Maxima of the \(Q\)-spectral radius of \(C_3 (C_4)\)-free graphs with given size and minimum degree \(\delta \geq 2\)
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• A spectral version of Mantel's theorem
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• The maximum outdegree power of complete \(k\)-partite oriented graphs
• A spectral extremal problem on non-bipartite triangle-free graphs
• Spectral radius of graphs with given size and odd girth
• Proof of a conjecture of V. Nikiforov
• The sum of the \(k\) largest distance eigenvalues of graphs
• Connected \((K_4 - e)\)-free graphs whose second largest eigenvalue does not exceed 1
• A spectral condition for odd cycles in non-bipartite graphs
• Maxima of the \(Q\)-index of non-bipartite \(C_3\)-free graphs
• Spectral extremal graphs for the bowtie
• Ordering the maxima of \(L\)-index and \(Q\)-index: graphs with given size and diameter
• A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
• The maximum spectral radius of graphs of given size with forbidden subgraph
• On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs
• The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
• On a generalization of the spectral Mantel's theorem
• Degree powers in \(K_{s,t}\)-minor free graphs
• Signed spectral Turań-type theorems
• Spectral radius, edge-disjoint cycles and cycles of the same length
• On the spectral radius of minimally 2-(edge)-connected graphs with given size
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Counting substructures and eigenvalues. I: Triangles
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• Spectral radius and the 2-power of Hamilton cycle
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• Spectral radius of graphs of given size with forbidden subgraphs
• A spectral Erdős-Rademacher theorem
• A Brualdi-Hoffman-Turán problem on cycles
• Spectral extremal results on trees
• A note on the signless Laplacian spectral ordering of graphs with given size
• Maxima of the \(Q\)-index of leaf-free graphs with given size
• Maxima of the Q ( L )-index of (minimally) 2-edge-connected graphs with given size
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• Maxima of the \(A_\alpha\)-spectral radius of graphs with given size and minimum degree \(\delta \ge 2\)
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• Maxima of the \(A_\alpha\)-index of graphs with given size and domination number
• The outdegree power of oriented graphs
• Ordering of graphs with fixed size and diameter by A _α -spectral radii

This page was built for publication: Eigenvalues and triangles in graphs

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