Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Zhai and Lin recently proved that if $G$ is an $n$-vertex connected $\theta(1, 2, r+1)$-free graph, then for odd $r$ and $n \geqslant 10r$, or for even $r$ and $n \geqslant 7r$, one has $\rho(G) \le \sqrt{\lfloor\frac{n^2}{4}\rfloor}$, and equality holds if and only if $G$ is $K_{\lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor}$. In this paper, for large enough $n$, we prove a sharp upper bound for the spectral radius in an $n$-vertex $H$-free non-bipartite graph, where $H$ is $\theta(1, 2, 3)$ or $\theta(1, 2, 4)$, and we characterize all the extremal graphs. Furthermore, for $n \geqslant 137$, we determine the maximum number of edges in an $n$-vertex $\theta(1, 2, 4)$-free non-bipartite graph and characterize the unique extremal graph.
Abstract
Zhai and Lin recently proved that if $G$ is an $n$-vertex connected $\theta(1, 2, r+1)$-free graph, then for odd $r$ and $n \geqslant 10r$, or for even $r$ and $n \geqslant 7r$, one has $\rho(G) \le \sqrt{\lfloor\frac{n^2}{4}\rfloor}$, and equality holds if and only if $G$ is $K_{\lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor}$. In this paper, for large enough $n$, we prove a sharp upper bound for the spectral radius in an $n$-vertex $H$-free non-bipartite graph, where $H$ is $\theta(1, 2, 3)$ or $\theta(1, 2, 4)$, and we characterize all the extremal graphs. Furthermore, for $n \geqslant 137$, we determine the maximum number of edges in an $n$-vertex $\theta(1, 2, 4)$-free non-bipartite graph and characterize the unique extremal graph.
참고문헌 (42)
- R. Aharoni, "k-free graphs and the connectivity of their independence complexes", J. Graph Theory, 83(4), pp.384~391 (2016)[DOI]
- L. Babai, "Spectral extrema for graphs: the Zarankiewicz problem", Electron. J. Combin, 16(1), pp.8~ (2009)[DOI]
- R. B. Bapat, "Graphs and Matrices, Universitext" (2010), Springer
- M. Bataineh, "Some extremal problems in graph theory", Ph.D, pp.2007
- M. S. A. Bataineh, "Edge-maximal graphs without θ5-graphs", Ars Combin, 124, pp.193~207 (2016)
- B. Bollob´as, "Cliques and the spectral radius", J. Combin. Theory Ser. B, 97(5), pp.859~865 (2007)[DOI]
- B. Bukh, "Tur´an numbers of theta graphs", Combin. Probab. Comput, 29(4), pp.495~507 (2020)[DOI]
- M. Z. Chen, "Spectral extremal results with forbidding linear forests", Graphs Combin, 35(1), pp.335~351 (2019)[DOI]
- M. Z. Chen, "On the spectral radius of graphs without a star forest", Discrete Math, 344(4), pp.12~ (2021)[DOI]
- S. Cioaba, "The maximum spectral radius of graphs without friendship subgraphs", Electron. J. Combin, 27(4), pp.19~ (2020)[DOI]
- P. Erdos, "A limit theorem in graph theory", Studia Sci. Math. Hungar, 1, pp.51~57 (1966)
- P. Erdos, "On the structure of linear graphs", Bull. Amer. Math. Soc, 52, pp.1087~1091 (1946)[DOI]
- R. J. Faudree, "On a class of degenerate extremal graph problems", Combinatorica, 3(1), pp.83~93 (1983)[DOI]
- Z. Furedi, "Extremal numbers for odd cycles", Combin. Probab. Comput, 24(4), pp.641~645 (2015)[DOI]
- Z. Furedi, "Erdos centennial" (2013), J´anos Bolyai Math. Soc
- H. Guo, "A spectral condition for the existence of a pentagon in non-bipartite graphs", Linear Algebra Appl, 627, pp.140~149 (2021)[DOI]
- M. M. M. Jaradat, "Edge-maximal graphs without θ2k+1-graphs", AKCE Int. J. Graphs Comb, 11(1), pp.57~65 (2014)
- R. Jia, "Some extremal problems in graph theory", Ph.D, pp.1998
- Y. Lan, "Extremal theta-free planar graphs", Discrete Math, 12342, pp.8~ (2019)[DOI]
- S. Li, "Characterizing P⩾2-factor and P⩾2-factor covered graphs with respect to the size or the spectral radius", Discrete Math, 344(11), pp.12~ (2021)[DOI]
- S. Li, "Adjacency eigenvalues of graphs without short odd cycles", Discrete Math, 345(1), pp.13~ (2022)[DOI]
- H. Lin, "A complete solution to the Cvetkovi´c-Rowlinson conjecture", J. Graph Theory, 97(3), pp.441~450 (2021)[DOI]
- H. Lin, "Eigenvalues and triangles in graphs", Combin. Probab. Comput, 30(2), pp.258~270 (2021)[DOI]
- H. Lu, "eigenvalues and regular factors", J. Graph Theory, 69(4), pp.349~355 (2012)[DOI]
- W. Mantel, "Problem 28", Wiskundige Opgaven, 10, pp.60~61 (1907)
- V. Nikiforov, "Some inequalities for the largest eigenvalue of a graph", Combin. Probab. Comput, 11(2), pp.179~189 (2002)[DOI]
- V. Nikiforov, "Bounds on graph eigenvalues II", Linear Algebra Appl, 427(2-3), pp.183~189 (2007)[DOI]
- V. Nikiforov, "A spectral condition for odd cycles in graphs", Linear Algebra Appl, 428(7), pp.1492~1498 (2008)[DOI]
- V. Nikiforov, "A contribution to the Zarankiewicz problem", Linear Algebra Appl, 432(6), pp.1405~1411 (2010)[DOI]
- V. Nikiforov, "The spectral radius of graphs without paths and cycles of specified length", Linear Algebra Appl, 432(9), pp.2243~2256 (2010)[DOI]
- V. Nikiforov, "Surveys in combinatorics 2011", pp.141~181 (2011), Cambridge Univ. Press
- E. Nosal, Eigenvalues of graphs, "Eigenvalues of graphs", Master, pp.1970
- M. Tait, "Three conjectures in extremal spectral graph theory", J. Combin. Theory Ser. B, 126, pp.137~161 (2017)[DOI]
- J. Verstraete, "Graphs without theta subgraphs", J. Combin. Theory Ser. B, 134, pp.76~87 (2019)[DOI]
- H. S. Wilf, "Spectral bounds for the clique and independence numbers of graphs", J. Combin. Theory Ser. B, 40(1), pp.113~117 (1986)[DOI]
- B. Wu, "The spectral radius of trees on k pendant vertices", Linear Algebra Appl, 395, pp.343~349 (2005)[DOI]
- L. You, "On the spectrum of an equitable quotient matrix and its application", Linear Algebra Appl, 577, pp.21~40 (2019)[DOI]
- M. Zhai, "On the Tur´an number of theta graphs", Graphs Combin, 37(6), pp.2155~2165 (2021)[DOI]
- M. Zhai, "Spectral extrema of graphs: forbidden hexagon", Discrete Math, 343(10), pp.6~ (2020)[DOI]
- M. Zhai, "A strengthening of the spectral chromatic critical edge theorem : books and theta graphs", J. Graph Theory, 102(3), pp.502~520 (2023)
- M. Zhai, "Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs", European J. Combin, 95, pp.18~ (2021)[DOI]
- M. Zhai, "Proof of a conjecture on the spectral radius of C4-free graphs", Linear Algebra Appl, 437(7), pp.1641~1647 (2012)[DOI]