Adjacency eigenvalues of graphs without short odd cycles

DOI10.1016/J.DISC.2021.112633MaRDI QIDQ2237217zbMATH OpenOpenAlexFDO

Authors Shuchao Li, Wanting Sun, Yuantian Yu

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalues short cycles

Mathematics Subject Classification ID

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

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

m a t h c a l G

be a set of graphs, we say

G

is extit{

m a t h c a l G

-free} if

G

does not contain any element of

m a t h c a l G

as a subgraph. Denote by

l a m b d a_{1}

and

l a m b d 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

l a m b d a_{1}^{2 k} + l a m b d a_{2}^{2 k}

of

n

-vertex

C_{3}, C_{5}, l d o t s, C_{2 k + 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

2 k + 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

2 k + 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].

Review text

The authors consider a classical spectral Turán-type problem. Let $G$ be a graph and let $\lambda_1$ and $\lambda_2$ denote the largest and second largest eigenvalues of the adjacency matrix $A(G)$ of $G$, respectively. In this paper, the authors focus on graphs without short cycles, according to the adjacency eigenvalues of the graph. First, an upper bound on $\lambda_1^{2k}+\lambda_2^{2k}$ for $n$-vertex graphs with no odd cycle of length at most $2k+1$ is established, and all corresponding extremal graphs are identified. Second, 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. Finally, the authors characterize the unique graph having maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3$. This last result solves an open problem proposed earlier by \textit{H. Lin} et al. [Comb. Probab. Comput. 30, No. 2, 258--270 (2020; Zbl 1466.05121)].

Recommendations

Cites work

Cited in

(40)

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)