Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius
Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius
Summary:
Let $G$ be a graph of order $n$ and $\lambda ( G) $ the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in $G$. One of the main results of the paper is the following theorem: \endgraf Let $k\geq 2,$ $n\geq k^{3}+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $\delta (G) \geq k.$ If \[ \lambda ( G) \geq n-k-1, \] then $G$ has a Hamiltonian cycle, unless $G=K_{1}\vee (K_{n-k-1}+K_{k})$ or $G=K_{k}\vee (K_{n-2k}+\bar {K}_{k}).$
References:
[1] Benediktovich, V. I.: Spectral condition for Hamiltonicity of a graph. Linear Algebra Appl. 494 (2016), 70-79. MR 3455686 | Zbl 1331.05125
[2] Bollob{á}s, B.: Modern Graph Theory. Graduate Texts in Mathematics 184 Springer, New York (1998). MR 1633290 | Zbl 0902.05016
[3] Bondy, J. A., Chvátal, V.: A method in graph theory. Discrete Math. 15 (1976), 111-135. DOI 10.1016/0012-365X(76)90078-9 | MR 0414429 | Zbl 0331.05138
[4] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Ann. Comb. 13 (2010), 403-412. DOI 10.1007/s00026-009-0039-4 | MR 2581094 | Zbl 1229.05193
[5] Chv{á}tal, V.: On Hamilton's ideals. J. Comb. Theory, Ser. B 12 (1972), 163-168. DOI 10.1016/0095-8956(72)90020-2 | Zbl 0213.50803
[6] Dirac, G. A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc., III. Ser. 2 (1952), 69-81. DOI 10.1112/plms/s3-2.1.69 | MR 0047308 | Zbl 0047.17001
[7] Erd{ő}s, P.: Remarks on a paper of Pósa. Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7 (1962), 227-229. MR 0184877 | Zbl 0114.40004
[8] Fan, Y.-Z., Yu, G.-D.: Spectral condition for a graph to be Hamiltonian with respect to normalized Laplacian. Preprint available at Arxiv 1207.6824v1 (2012), 12 pages.
[9] Fiedler, M., Nikiforov, V.: Spectral radius and Hamiltonicity of graphs. Linear Algebra Appl. 432 (2010), 2170-2173. DOI 10.1016/j.laa.2009.01.005 | MR 2599851 | Zbl 1218.05091
[10] Hong, Y., Shu, J.-L., Fang, K.: A sharp upper bound of the spectral radius of graphs. J. Comb. Theory, Ser. B 81 (2001), 177-183. DOI 10.1006/jctb.2000.1997 | MR 1814902 | Zbl 1024.05059
[11] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42 (2003), 17-33. DOI 10.1002/jgt.10065 | MR 1943104 | Zbl 1028.05059
[12] Li, R.: Laplacian spectral radius and some Hamiltonian properties of graphs. Appl. Math. E-Notes (electronic only) 14 216-220 (2014), corrigendum, ibid. 15 216-217 (2015). MR 3310116 | Zbl 1333.05183
[13] Li, B., Ning, B.: Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles. Linear Multilinear Algebra DOI:10.1080/03081087.2016.1151854. DOI 10.1080/03081087.2016.1151854 | MR 3539577
[14] Liu, R., Shiu, W. C., Xue, J.: Sufficient spectral conditions on Hamiltonian and traceable graphs. Linear Algebra Appl. 467 (2015), 254-266. MR 3284812 | Zbl 1304.05094
[15] Lu, M., Liu, H., Tian, F.: Spectral radius and Hamiltonian graphs. Linear Algebra Appl. 437 (2012), 1670-1674. MR 2946350 | Zbl 1247.05129
[16] Nikiforov, V.: Some inequalities for the largest eigenvalue of a graph. Comb. Probab. Comput. 11 (2002), 179-189. DOI 10.1017/S0963548301004928 | MR 1888908 | Zbl 1005.05029
[17] Ning, B., Ge, J.: Spectral radius and Hamiltonian properties of graphs. Linear Multilinear Algebra 63 (2015), 1520-1530. DOI 10.1080/03081087.2014.947984 | MR 3304990 | Zbl 1332.05091
[18] Ore, O.: Hamilton connected graphs. J. Math. Pures Appl., IX. Sér. 42 (1963), 21-27. MR 0146816 | Zbl 0106.37103
[19] Ore, O.: Arc coverings of graphs. Ann. Mat. Pura Appl., IV. Ser. 55 (1961), 315-321. DOI 10.1007/BF02412090 | MR 0162242 | Zbl 0103.39702
[20] Zhou, B.: Signless Laplacian spectral radius and Hamiltonicity. Linear Algebra Appl. 432 (2010), 566-570. MR 2577702 | Zbl 1188.05086
Search
Partner of
