Adjacency eigenvalues of graphs without short odd cycles

DOI10.1016/J.DISC.2021.112633zbMATH Open1480.05086arXiv2109.04599OpenAlexW3204462599MaRDI QIDQ2237217FDOQ2237217

Authors: Shuchao Li, Wanting Sun, Yuantian Yu 

Publication date: 27 October 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: It is well known that spectral Tur'{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur'{a}n type problem. Let $G$ be a graph and let $mathcalG$ be a set of graphs, we say $G$ is extit{$mathcalG$-free} if $G$ does not contain any element of $mathcalG$ as a subgraph. Denote by $lambd{a}_1$ and $lambd{a}_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $lambd{a}_1^{2k}+lambd{a}_2^{2k}$ of $n$-vertex $C_3,C_5,ldots,C_{2k+1}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270].

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

Recommendations

• Proof of conjectures on adjacency eigenvalues of graphs
• On graphs with distinct eigenvalues
• A note on graphs without short even cycles
• The spectral radius of graphs without long cycles
• The spectral radius of graphs with no intersecting odd cycles
• scientific article; zbMATH DE number 459300
• Some observations on the smallest adjacency eigenvalue of a graph
• Eigenvalue multiplicity in triangle-free graphs
• On graphs with exactly one anti-adjacency eigenvalue and beyond

zbMATH Keywords

eigenvaluesshort cycles

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• A sharp upper bound of the spectral radius of graphs
• Some Inequalities for the Largest Eigenvalue of a Graph
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Spectra of graphs
• The spectral radius of graphs without paths and cycles of specified length
• On the spectral radius of (0,1)-matrices
• Pancyclic graphs. I
• Über ein Problem von K. Zarankiewicz
• On a problem of K. Zarankiewicz
• Cycles of even length in graphs
• Bipartite graphs with at most six non-zero eigenvalues
• Bounds on graph eigenvalues. II
• A contribution to the Zarankiewicz problem
• On the Turán number for the hexagon
• A bound on the spectral radius of graphs
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• On the theory of graphs
• Large cycles in graphs
• Cliques and the spectral radius
• On a conjecture concerning spanning tree invariants and loop systems
• Walks and the spectral radius of graphs
• On the number of edges of quadrilateral-free graphs
• Sufficient Conditions for Circuits in Graphs^†
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Bounds of eigenvalues of a graph
• A bound on the spectral radius of graphs with \(e\) edges
• Independence, odd girth, and average degree
• Title not available (Why is that?)
• The maximum spectral radius of \(C_4\)-free graphs of given order and size
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• The independence number of dense graphs with large odd girth
• Upper bounds for the achromatic and coloring numbers of a graph
• Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph
• Bisections of graphs without short cycles
• Extremal numbers for odd cycles
• Spectral extrema of graphs: forbidden hexagon
• Graphs without short odd cycles are nearly bipartite
• Maximum bisections of graphs without short even cycles
• Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• Eigenvalues and triangles in graphs
• Adjacency eigenvalues of graphs without short odd cycles
• Vertex colorings of graphs without short odd cycles

Cited In (31)

• Adjacency eigenvalues of graphs without short odd cycles
• The spectral radius of graphs with no odd wheels
• A spectral condition for odd cycles in graphs
• Maxima of the \(Q\)-index of non-bipartite graphs: forbidden short odd cycles
• A spectral Erdős-Rademacher theorem
• The spectral radius of graphs without paths and cycles of specified length
• Maxima of the \(Q\)-index of leaf-free graphs with given size
• The index of signed graphs with forbidden subgraphs
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• On the spectral Turán problem of theta graphs
• Signless Laplacian spectral radius of graphs without short cycles or long cycles
• Complete characterization of path-factor and path-factor covered graphs via Q -index and D -index
• Refinement on Spectral Turán’s Theorem
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• Spectral extremal graphs without intersecting triangles as a minor
• Path factors in bipartite graphs from size or spectral radius
• A spectral extremal problem on non-bipartite triangle-free graphs
• Spectral radius of graphs with given size and odd girth
• Spectral extremal problem on disjoint color-critical graphs
• Title not available (Why is that?)
• A spectral condition for odd cycles in non-bipartite 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 \(\{C_3, C_5\}\)-free graphs of given size
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• Spectral radius, edge-disjoint cycles and cycles of the same length
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• On the \(A_\alpha\)-spectral radius of graphs without large matchings
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles

This page was built for publication: Adjacency eigenvalues of graphs without short odd cycles

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