Document Zbl 1446.05064 - zbMATH Open
On sufficient spectral radius conditions for Hamiltonicity of \(k\)-connected graphs. (English) Zbl 1446.05064
Summary: In this paper, we present two new sufficient conditions on the spectral radius \(\rho(G)\) that guarantee the Hamiltonicity and traceability of a \(k\)-connected graph \(G\) of sufficiently large order, respectively, unless \(G\) is a specified exceptional graph. In particular, if \(k\geq 2\), \(n\geq k^3+k+2\), and \(\rho(G)>n-k-1-\frac{1}{n}\), then \(G\) is Hamiltonian, unless \(G\) is a specified exceptional graph. If \(k\geq 1\), \(n\geq k^3+k^2+k+3\), and \(\rho(G)>n-k-2-\frac{1}{n}\), then \(G\) is traceable, unless \(G\) is a specified exceptional graph.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C40 | Connectivity |
References:
| [1] | Benediktovich, V. I., Spectral condition for hamiltonicity of a graph, Linear Algebra Appl., 494, 70-79 (2016) · Zbl 1331.05125 |
| [2] | Bondy, J. A.; Chvátal, V., A method in graph theory, Discrete Math., 15, 111-135 (1976) · Zbl 0331.05138 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory, Grad. Texts in Math., vol. 244 (2008), Springer: Springer New York · Zbl 1134.05001 |
| [4] | Brouwer, A. E.; Haemers, W. H., Spectra of Graphs (2011), Springer-Verlag |
| [5] | Chvátal, V.; Erdős, P., A note on hamiltonian circuits, Discrete Math., 2, 111-113 (1972) · Zbl 0233.05123 |
| [6] | Fiedler, M.; Nikiforov, V., Spectral radius and hamiltonicity of graphs, Linear Algebra Appl., 432, 2170-2173 (2010) · Zbl 1218.05091 |
| [7] | Ge, J.; Ning, B., Spectral radius and hamiltonian properties of graphs, II, Linear Multilinear Algebra (2019), published online |
| [8] | Godsil, C.; Royle, C., Algebraic Graph Theory (2001), Springer · Zbl 1026.05046 |
| [9] | Hong, Y.; Shu, J. L.; Fang, K. F., A sharp upper bound of the spectral radius of graphs, J. Comb. Theory, Ser. B, 81, 177-183 (2001) · Zbl 1024.05059 |
| [10] | Li, B. L.; Ning, B., Spectral analogues of Erdős’ and Moon-Moser’s theorems on Hamilton cycles, Linear Multilinear Algebra, 64, 2252-2269 (2016) · Zbl 1352.05105 |
| [11] | Li, R., The largest eigenvalue and some hamiltonian properties of graphs, Electron. J. Linear Algebra, 34, 389-392 (2018) · Zbl 1396.05072 |
| [12] | Liu, R. F.; Shiu, W. C.; Xue, J., Sufficient spectral conditions on hamiltonian and traceable graphs, Linear Algebra Appl., 467, 254-266 (2015) · Zbl 1304.05094 |
| [13] | Lu, M.; Liu, H. Q.; Tian, F., Spectral radius and hamiltonian graphs, Linear Algebra Appl., 437, 1670-1674 (2012) · Zbl 1247.05129 |
| [14] | Nikiforov, V., Some inequalities for the largest eigenvalue of a graph, Comb. Probab. Comput., 11, 179-189 (2002) · Zbl 1005.05029 |
| [15] | Nikiforov, V., Spectral radius and hamiltonicity of graphs with large minimum degree, Czechoslov. Math. J., 66, 925-940 (2016) · Zbl 1413.05242 |
| [16] | Ning, B.; Ge, J., Spectral radius and hamiltonian properties of graphs, Linear Multilinear Algebra, 63, 1520-1530 (2015) · Zbl 1332.05091 |
| [17] | Prasolov, V. V., Polynomials (2001), MTSNMO: MTSNMO Moscow |
| [18] | Zhou, B., Signless Laplacian spectral radius and hamiltonicity, Linear Algebra Appl., 432, 566-570 (2010) · Zbl 1188.05086 |
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.