×

Signless Laplacian eigenvalues and circumference of graphs. (English) Zbl 1287.05086

Summary: In this paper, we investigate the relation between the \(Q\)-spectrum and the structure of \(G\) in terms of the circumference of \(G\). Exploiting this relation, we give a novel necessary condition for a graph to be Hamiltonian by means of its \(Q\)-spectrum. We also determine the graphs with exactly one or two \(Q\)-eigenvalues greater than or equal to 2 and obtain all minimal forbidden subgraphs and maximal graphs, as induced subgraphs, with respect to the latter property.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C22 Signed and weighted graphs
05C45 Eulerian and Hamiltonian graphs
05C35 Extremal problems in graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland Amsterdam · Zbl 1226.05083
[2] Butler, S.; Chung, F., Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Ann. Comb., 13, 403-412 (2010) · Zbl 1229.05193
[3] Cvetković, D.; Rowlinson, P.; Simić, S. K., Signless Laplacian of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061
[4] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, I, Publ. Inst. Math. (Beograd) (N.S.), 85, 99, 19-33 (2009) · Zbl 1224.05293
[5] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, II, Linear Algebra Appl., 432, 2257-2272 (2010) · Zbl 1218.05089
[6] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, III, Appl. Anal. Discrete Math., 4, 156-166 (2010) · Zbl 1265.05360
[7] Fan, Y.-Z.; Gong, S.-C.; Zhou, J.; Tan, Y.-Y.; Wang, Yi, Nonsingular mixed graphs with few eigenvalues greater than two, European J. Combin., 28, 1694-1702 (2007) · Zbl 1122.05058
[8] Fan, Y. Z.; Li, J. S., On graphs with small number of Laplacian eigenvalues greater than two, Linear Algebra Appl., 360, 207-213 (2003) · Zbl 1015.05048
[9] Fiedler, M.; Nikiforov, V., Spectral radius and Hamiltonicity of graphs, Linear Algebra Appl., 432, 2170-2173 (2010) · Zbl 1218.05091
[10] Gould, R. J., Advances on the Hamiltonian problem—a survey, Graphs Combin., 19, 7-52 (2003) · Zbl 1024.05057
[11] Grone, R.; Merris, R.; Sunder, V. S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11, 218-238 (1990) · Zbl 0733.05060
[12] Guo, J. M.; Tan, S. W., A relation between the matching number and Laplacian spectrum of a graph, Linear Algebra Appl., 325, 71-74 (2001)
[13] Gutman, I.; Babić, D.; Gineityte, V., Degeneracy in the equivalent bond orbital model for high-energy band in the photoelectron spectra of saturated hydrocarbons, ACH Models Chem., 135, 901-909 (1998)
[14] Gutman, I.; Gineitite, V.; Lepović, M.; Petrović, M., The high-energy band in the photoelectron spectrum of alkanes and its dependence on molecular structure, J. Serb. Chem. Soc., 64, 673-680 (1999)
[15] Haemers, W. H.; Spence, E., Enumeration of cospectral graphs, European J. Combin., 25, 199-211 (2004) · Zbl 1033.05070
[16] Krivelevich, M.; Sudakov, B., Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory, 42, 17-33 (2003) · Zbl 1028.05059
[17] Lu, M.; Liu, H. Q.; Tian, F., Spectral radius and Hamiltonian graphs, Linear Algebra Appl., 437, 1670-1674 (2012) · Zbl 1247.05129
[18] Mohar, B., A domain monotonicity theorem for graphs and hamiltonicity, Discrete Appl. Math., 36, 169-177 (1992) · Zbl 0765.05071
[19] Petrović, M.; Borovićanin, B.; Torgašev, A., On graphs with at most three Laplacian eigenvalues greater than or equal to two, Linear Algebra Appl., 380, 173-184 (2004) · Zbl 1034.05033
[20] Petrović, M.; Gutman, I.; Lepović, M.; Milekić, B., On bipartite graphs with small number of Laplacian eigenvalues greater than two and three, Linear Multilinear Algebra, 47, 205-215 (1999) · Zbl 0964.05040
[21] van den Heuvel, J., Hamilton cycle and eigenvalueso of graphs, Linear Algebra Appl., 226-228, 723-730 (1995) · Zbl 0846.05059
[22] Wang, J. F.; Belardo, F., A note on the signless Laplacian eigenvalues of graphs, Linear Algebra Appl., 435, 2585-2590 (2011) · Zbl 1225.05176
[23] Zhang, X. D., Graphs with fourth Laplacian eigenvalue less than two, European J. Combin., 24, 617-630 (2003) · Zbl 1028.05064
[24] Zhang, X. D., Graphs characterized by Laplacian eigenvalues, Chin. Ann. Math. Ser. B, 25, 1, 103-110 (2004) · Zbl 1043.05081
[25] 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.