Spectral radius of graphs of given size with forbidden subgraphs. (English) Zbl 1535.05176
Summary: Let \(\rho (G)\) be the spectral radius of a graph \(G\) with \(m\) edges. Let \(S_{m-k+1}^k\) be the graph obtained from \(K_{1, m-k}\) by adding \(k\) disjoint edges within its independent set. Nosal’s theorem states that if \(\rho (G)>\sqrt{m}\), then \(G\) contains a triangle. M. Zhai and J. Shu [Discrete Math. 345, No. 1, Article ID 112630, 10 p. (2022; Zbl 1476.05130)] showed that any non-bipartite graph \(G\) with \(m \geq 26\) and \(\rho (G) \geq \rho (S_m^1) > \sqrt{m-1}\) contains a quadrilateral unless \(G \cong S_m^1\). Z. Wang [ibid. 345, No. 9, Article ID 112973, 12 p. (2022; Zbl 1496.05106)] proved that if \(\rho (G) \geq \sqrt{m-1}\) for a graph \(G\) with size \(m \geq 27\), then \(G\) contains a quadrilateral unless \(G\) is one out of four exceptional graphs. In this paper, we show that any non-bipartite graph \(G\) with size \(m \geq 51\) and \(\rho (G) \geq \rho (S_{m-1}^2) >\sqrt{m-2}\) contains a quadrilateral unless \(G \cong S_m^1\) or \(G \cong S_{m-1}^2\). Moreover, we show that if \(\rho (G) \geq \rho (S_{\frac{m+4}{2}, 2}^-)\) for a graph \(G\) with even size \(m \geq 74\), then \(G\) contains a \(C_5^+\) unless \(G \cong S_{\frac{m+4}{2}, 2}^-\), where \(C_t^+\) denotes the graph obtained from \(C_t\) and \(C_3\) by identifying an edge, \(S_{n, k}\) denotes the graph obtained by joining every vertex of \(K_k\) to \(n - k\) isolated vertices and \(S_{n,k}^-\) denotes the graph obtained from \(S_{n,k}\) by deleting an edge incident to a vertex of degree \(k\), respectively.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C35 | Extremal problems in graph theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
References:
| [1] | Brualdi, R. A.; Hoffman, A. J., On the spectral radius of \((0, 1)\) matrices, Linear Algebra Appl., 65, 133-146, 1985 · Zbl 0563.15012 |
| [2] | Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 244, 2008, Springer: Springer New York) · Zbl 1134.05001 |
| [3] | Chen, M. Z.; Liu, A. M.; Zhang, X.-D., On the spectral radius of graphs without a star forest, Discrete Math., 344, Article 112269 pp., 2021 · Zbl 1460.05109 |
| [4] | Chen, M. Z.; Zhang, X.-D., Some new results and problems in spectral extremal graph theory, J. Anhui Univ. Nat. Sci., 42, 12-25, 2018, (in Chinese) · Zbl 1399.05121 |
| [5] | Cioabă, S. M.; Desai, D. N.; Tait, M., The spectral radius of graphs with no odd wheels, Eur. J. Comb., 99, Article 103420 pp., 2022 · Zbl 1480.05085 |
| [6] | Cioabǎ, S. M.; Feng, L. H.; Michael, T.; Zhang, X.-D., The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Comb., 27, 2020, #P4.22 · Zbl 1453.05059 |
| [7] | Cvektović, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra, 2010, Cambridge University Press: Cambridge University Press New York · Zbl 1211.05002 |
| [8] | Fang, X. N.; You, L. H., The maximum spectral radius of graphs of given size with forbidden subgraph, Linear Algebra Appl., 666, 114-128, 2023 · Zbl 1511.05137 |
| [9] | Füredi, Z.; Simonovits, M., The history of degenerate (bipartite) extremal graph problems, Erdős centennial, Bolyai Soc. Math. Stud., 25, 169-264, 2013 · Zbl 1296.05098 |
| [10] | Guo, H. T.; Lin, H. Q.; Zhao, Y. H., A spectral condition for the existence of a pentagon in non-bipartite graphs, Linear Algebra Appl., 627, 140-149, 2021 · Zbl 1468.05153 |
| [11] | Li, S. C.; Sun, W. T.; Wei, W., Forbidden subgraphs, bounded spectral radii, and size of graphs |
| [12] | Li, Y. T.; Liu, W. J.; Feng, L. H., A survey on spectral conditions for some extremal graph problems, Adv. Math. (China), 51, 2, 193-258, 2022 · Zbl 07887871 |
| [13] | Li, Y. T.; Peng, Y. J., The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, Electron. J. Comb., 29, 4, P4.2, 2022 · Zbl 1503.05078 |
| [14] | Lin, H. Q.; Guo, H. T., A spectral condition for odd cycles in non-bipartite graphs, Linear Algebra Appl., 631, 83-93, 2021 · Zbl 1483.05095 |
| [15] | Lin, H. Q.; Ning, B.; Wu, B. Y.D. R., Eigenvalues and triangles in graphs, Comb. Probab. Comput., 30, 2, 258-270, 2021 · Zbl 1466.05121 |
| [16] | Liu, X. X.; Broersma, H.; Wang, L. G., On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees, Discrete Math., 345, 12, Article 113112 pp., 2022 · Zbl 1497.05154 |
| [17] | Min, G.; Lou, Z. Z.; Huang, Q. X., A sharp upper bound on the spectral radius of \(C_5\)-free/\( C_6\)-free graphs with given size, Linear Algebra Appl., 640, 162-178, 2022 · Zbl 1485.05104 |
| [18] | Nikiforov, V., The maximum spectral radius of \(C_4\)-free graphs of given order and size, Linear Algebra Appl., 430, 2898-2905, 2009 · Zbl 1169.05350 |
| [19] | Nikiforov, V., The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl., 432, 2243-2256, 2010 · Zbl 1217.05152 |
| [20] | Nikiforov, V., Some new results in extremal graph theory, Lond. Math. Soc. Lect. Note Ser., 392, 141-181, 2011 · Zbl 1244.05125 |
| [21] | Nosal, E., Eigenvalues of Graphs, 1970, University of Calgary, Master’s Thesis |
| [22] | Wang, Z. W., Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals, Discrete Math., 345, Article 112973 pp., 2022 · Zbl 1496.05106 |
| [23] | Zhai, M. Q.; Lin, H. Q., Spectral extrema of graphs: forbidden hexagon, Discrete Math., 343, Article 112028 pp., 2020 · Zbl 1445.05055 |
| [24] | Zhai, M. Q.; Lin, H. Q.; Shu, J. L., Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs, Eur. J. Comb., 95, Article 103322 pp., 2021 · Zbl 1475.05113 |
| [25] | Zhai, M. Q.; Shu, J. L., A spectral version of Mantel’s theorem, Discrete Math., 345, Article 112630 pp., 2022 · Zbl 1476.05130 |
| [26] | Zhai, M. Q.; Wang, B., Proof of a conjecture on the spectral radius of \(C_4\)-free graphs, Linear Algebra Appl., 437, 1641-1647, 2012 · Zbl 1247.05145 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
