Back to Search
Start Over
Adjacency eigenvalues of graphs without short odd cycles
- Source :
- Discrete Mathematics. 345:112633
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
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 $\mathcal{G}$ be a set of graphs, we say $G$ is \textit{$\mathcal{G}$-free} if $G$ does not contain any element of $\mathcal{G}$ as a subgraph. Denote by $\lambda_1$ and $\lambda_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 $\lambda_1^{2k}+\lambda_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].<br />Comment: 15 pages. It is accepted by Discrete Mathematics
- Subjects :
- Discrete mathematics
Spectral radius
Graph theory
Girth (graph theory)
Type (model theory)
Upper and lower bounds
Theoretical Computer Science
Combinatorics
Integer
Computer Science::Discrete Mathematics
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Adjacency list
Combinatorics (math.CO)
Adjacency matrix
05C50, 05C35
Mathematics
Subjects
Details
- ISSN :
- 0012365X
- Volume :
- 345
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....ccfd66dd6faaf560782380fd05935b52