| Title:
|
Spectral radius and Hamiltonicity of graphs with large minimum degree (English) |
| Author:
|
Nikiforov, Vladimir |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
925-940 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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}).$ (English) |
| Keyword:
|
Hamiltonian cycle |
| Keyword:
|
Hamiltonian path |
| Keyword:
|
minimum degree |
| Keyword:
|
spectral radius |
| MSC:
|
05C35 |
| MSC:
|
05C50 |
| idZBL:
|
Zbl 06644042 |
| idMR:
|
MR3556876 |
| DOI:
|
10.1007/s10587-016-0301-y |
| . |
| Date available:
|
2016-10-01T15:37:45Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145880 |
| . |
| Reference:
|
[1] Benediktovich, V. I.: Spectral condition for Hamiltonicity of a graph.Linear Algebra Appl. 494 (2016), 70-79. Zbl 1331.05125, MR 3455686 |
| Reference:
|
[2] Bollob{á}s, B.: Modern Graph Theory.Graduate Texts in Mathematics 184 Springer, New York (1998). Zbl 0902.05016, MR 1633290 |
| Reference:
|
[3] Bondy, J. A., Chvátal, V.: A method in graph theory.Discrete Math. 15 (1976), 111-135. Zbl 0331.05138, MR 0414429, 10.1016/0012-365X(76)90078-9 |
| Reference:
|
[4] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian.Ann. Comb. 13 (2010), 403-412. Zbl 1229.05193, MR 2581094, 10.1007/s00026-009-0039-4 |
| Reference:
|
[5] Chv{á}tal, V.: On Hamilton's ideals.J. Comb. Theory, Ser. B 12 (1972), 163-168. Zbl 0213.50803, 10.1016/0095-8956(72)90020-2 |
| Reference:
|
[6] Dirac, G. A.: Some theorems on abstract graphs.Proc. Lond. Math. Soc., III. Ser. 2 (1952), 69-81. Zbl 0047.17001, MR 0047308, 10.1112/plms/s3-2.1.69 |
| Reference:
|
[7] Erd{ő}s, P.: Remarks on a paper of Pósa.Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7 (1962), 227-229. Zbl 0114.40004, MR 0184877 |
| Reference:
|
[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. |
| Reference:
|
[9] Fiedler, M., Nikiforov, V.: Spectral radius and Hamiltonicity of graphs.Linear Algebra Appl. 432 (2010), 2170-2173. Zbl 1218.05091, MR 2599851, 10.1016/j.laa.2009.01.005 |
| Reference:
|
[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. Zbl 1024.05059, MR 1814902, 10.1006/jctb.2000.1997 |
| Reference:
|
[11] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian.J. Graph Theory 42 (2003), 17-33. Zbl 1028.05059, MR 1943104, 10.1002/jgt.10065 |
| Reference:
|
[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). Zbl 1333.05183, MR 3310116 |
| Reference:
|
[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. MR 3539577, 10.1080/03081087.2016.1151854 |
| Reference:
|
[14] Liu, R., Shiu, W. C., Xue, J.: Sufficient spectral conditions on Hamiltonian and traceable graphs.Linear Algebra Appl. 467 (2015), 254-266. Zbl 1304.05094, MR 3284812 |
| Reference:
|
[15] Lu, M., Liu, H., Tian, F.: Spectral radius and Hamiltonian graphs.Linear Algebra Appl. 437 (2012), 1670-1674. Zbl 1247.05129, MR 2946350 |
| Reference:
|
[16] Nikiforov, V.: Some inequalities for the largest eigenvalue of a graph.Comb. Probab. Comput. 11 (2002), 179-189. Zbl 1005.05029, MR 1888908, 10.1017/S0963548301004928 |
| Reference:
|
[17] Ning, B., Ge, J.: Spectral radius and Hamiltonian properties of graphs.Linear Multilinear Algebra 63 (2015), 1520-1530. Zbl 1332.05091, MR 3304990, 10.1080/03081087.2014.947984 |
| Reference:
|
[18] Ore, O.: Hamilton connected graphs.J. Math. Pures Appl., IX. Sér. 42 (1963), 21-27. Zbl 0106.37103, MR 0146816 |
| Reference:
|
[19] Ore, O.: Arc coverings of graphs.Ann. Mat. Pura Appl., IV. Ser. 55 (1961), 315-321. Zbl 0103.39702, MR 0162242, 10.1007/BF02412090 |
| Reference:
|
[20] Zhou, B.: Signless Laplacian spectral radius and Hamiltonicity.Linear Algebra Appl. 432 (2010), 566-570. Zbl 1188.05086, MR 2577702 |
| . |
