A spectral extremal problem on non-bipartite triangle-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909134287273984 |
|---|---|
| author | Li, Yongtao Feng, Lihua Peng, Yuejian |
| author_facet | Li, Yongtao Feng, Lihua Peng, Yuejian |
| contents | A theorem of Nosal and Nikiforov states that if $G$ is a triangle-free graph with $m$ edges, then $λ(G)\le \sqrt{m}$, where the equality holds if and only if $G$ is a complete bipartite graph. A well-known spectral conjecture of Bollobás and Nikiforov [J. Combin. Theory Ser. B 97 (2007)] asserts that if $G$ is a $K_{r+1}$-free graph with $m$ edges, then $λ_1^2(G) + λ_2^2(G) \le (1-\frac{1}{r})2m$. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] confirmed the conjecture in the case $r=2$. Using this base case, they proved further that $λ(G)\le \sqrt{m-1}$ for every non-bipartite triangle-free graph $G$, with equality if and only if $m=5$ and $G=C_5$. Moreover, Zhai and Shu [Discrete Math. 345 (2022)] presented an improvement by showing $λ(G) \le β(m)$, where $β(m)$ is the largest root of $Z(x):=x^3-x^2-(m-2)x+m-3$. The equality in Zhai--Shu's result holds only if $m$ is odd and $G$ is obtained from the complete bipartite graph $K_{2,\frac{m-1}{2}}$ by subdividing exactly one edge. Motivated by this observation, Zhai and Shu proposed a question to find a sharp bound when $m$ is even. We shall solve this question by using a different method and characterize three kinds of spectral extremal graphs over all triangle-free non-bipartite graphs with even size. Our proof technique is mainly based on applying Cauchy interlacing theorem of eigenvalues of a graph, and with the aid of a triangle counting lemma in terms of both eigenvalues and the size of a graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_00716 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A spectral extremal problem on non-bipartite triangle-free graphs Li, Yongtao Feng, Lihua Peng, Yuejian Combinatorics 05C50, 05C35 A theorem of Nosal and Nikiforov states that if $G$ is a triangle-free graph with $m$ edges, then $λ(G)\le \sqrt{m}$, where the equality holds if and only if $G$ is a complete bipartite graph. A well-known spectral conjecture of Bollobás and Nikiforov [J. Combin. Theory Ser. B 97 (2007)] asserts that if $G$ is a $K_{r+1}$-free graph with $m$ edges, then $λ_1^2(G) + λ_2^2(G) \le (1-\frac{1}{r})2m$. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] confirmed the conjecture in the case $r=2$. Using this base case, they proved further that $λ(G)\le \sqrt{m-1}$ for every non-bipartite triangle-free graph $G$, with equality if and only if $m=5$ and $G=C_5$. Moreover, Zhai and Shu [Discrete Math. 345 (2022)] presented an improvement by showing $λ(G) \le β(m)$, where $β(m)$ is the largest root of $Z(x):=x^3-x^2-(m-2)x+m-3$. The equality in Zhai--Shu's result holds only if $m$ is odd and $G$ is obtained from the complete bipartite graph $K_{2,\frac{m-1}{2}}$ by subdividing exactly one edge. Motivated by this observation, Zhai and Shu proposed a question to find a sharp bound when $m$ is even. We shall solve this question by using a different method and characterize three kinds of spectral extremal graphs over all triangle-free non-bipartite graphs with even size. Our proof technique is mainly based on applying Cauchy interlacing theorem of eigenvalues of a graph, and with the aid of a triangle counting lemma in terms of both eigenvalues and the size of a graph. |
| title | A spectral extremal problem on non-bipartite triangle-free graphs |
| topic | Combinatorics 05C50, 05C35 |
| url | https://arxiv.org/abs/2304.00716 |