Spectral radius and Hamiltonicity of graphs with large minimum degree

Vladimir Nikiforov

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 925-940
  • ISSN: 0011-4642

Abstract

top
Let G be a graph of order n and λ ( 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: Let k 2 , n k 3 + k + 4 , and let G be a graph of order n , with minimum degree δ ( G ) k . If λ ( G ) n - k - 1 , then G has a Hamiltonian cycle, unless G = K 1 ( K n - k - 1 + K k ) or G = K k ( K n - 2 k + K ¯ k ) .

How to cite

top

Nikiforov, Vladimir. "Spectral radius and Hamiltonicity of graphs with large minimum degree." Czechoslovak Mathematical Journal 66.3 (2016): 925-940. <http://eudml.org/doc/286808>.

@article{Nikiforov2016,
abstract = {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: Let $k\ge 2,$$n\ge k^\{3\}+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $\delta (G) \ge k.$ If \[ \lambda ( G) \ge 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\}).$},
author = {Nikiforov, Vladimir},
journal = {Czechoslovak Mathematical Journal},
keywords = {Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius},
language = {eng},
number = {3},
pages = {925-940},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Spectral radius and Hamiltonicity of graphs with large minimum degree},
url = {http://eudml.org/doc/286808},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Nikiforov, Vladimir
TI - Spectral radius and Hamiltonicity of graphs with large minimum degree
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 925
EP - 940
AB - 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: Let $k\ge 2,$$n\ge k^{3}+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $\delta (G) \ge k.$ If \[ \lambda ( G) \ge 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}).$
LA - eng
KW - Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius
UR - http://eudml.org/doc/286808
ER -

References

top
  1. Benediktovich, V. I., Spectral condition for Hamiltonicity of a graph, Linear Algebra Appl. 494 (2016), 70-79. (2016) Zbl1331.05125MR3455686
  2. Bollob{á}s, B., Modern Graph Theory, Graduate Texts in Mathematics 184 Springer, New York (1998). (1998) Zbl0902.05016MR1633290
  3. Bondy, J. A., Chvátal, V., 10.1016/0012-365X(76)90078-9, Discrete Math. 15 (1976), 111-135. (1976) Zbl0331.05138MR0414429DOI10.1016/0012-365X(76)90078-9
  4. Butler, S., Chung, F., 10.1007/s00026-009-0039-4, Ann. Comb. 13 (2010), 403-412. (2010) Zbl1229.05193MR2581094DOI10.1007/s00026-009-0039-4
  5. Chv{á}tal, V., 10.1016/0095-8956(72)90020-2, J. Comb. Theory, Ser. B 12 (1972), 163-168. (1972) Zbl0213.50803DOI10.1016/0095-8956(72)90020-2
  6. Dirac, G. A., 10.1112/plms/s3-2.1.69, Proc. Lond. Math. Soc., III. Ser. 2 (1952), 69-81. (1952) Zbl0047.17001MR0047308DOI10.1112/plms/s3-2.1.69
  7. Erd{ő}s, P., Remarks on a paper of Pósa, Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7 (1962), 227-229. (1962) Zbl0114.40004MR0184877
  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. (2012) 
  9. Fiedler, M., Nikiforov, V., 10.1016/j.laa.2009.01.005, Linear Algebra Appl. 432 (2010), 2170-2173. (2010) Zbl1218.05091MR2599851DOI10.1016/j.laa.2009.01.005
  10. Hong, Y., Shu, J.-L., Fang, K., 10.1006/jctb.2000.1997, J. Comb. Theory, Ser. B 81 (2001), 177-183. (2001) Zbl1024.05059MR1814902DOI10.1006/jctb.2000.1997
  11. Krivelevich, M., Sudakov, B., 10.1002/jgt.10065, J. Graph Theory 42 (2003), 17-33. (2003) Zbl1028.05059MR1943104DOI10.1002/jgt.10065
  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). (2015) Zbl1333.05183MR3310116
  13. Li, B., Ning, B., 10.1080/03081087.2016.1151854, Linear Multilinear Algebra DOI:10.1080/03081087.2016.1151854. MR3539577DOI10.1080/03081087.2016.1151854
  14. Liu, R., Shiu, W. C., Xue, J., Sufficient spectral conditions on Hamiltonian and traceable graphs, Linear Algebra Appl. 467 (2015), 254-266. (2015) Zbl1304.05094MR3284812
  15. Lu, M., Liu, H., Tian, F., Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (2012), 1670-1674. (2012) Zbl1247.05129MR2946350
  16. Nikiforov, V., 10.1017/S0963548301004928, Comb. Probab. Comput. 11 (2002), 179-189. (2002) Zbl1005.05029MR1888908DOI10.1017/S0963548301004928
  17. Ning, B., Ge, J., 10.1080/03081087.2014.947984, Linear Multilinear Algebra 63 (2015), 1520-1530. (2015) Zbl1332.05091MR3304990DOI10.1080/03081087.2014.947984
  18. Ore, O., Hamilton connected graphs, J. Math. Pures Appl., IX. Sér. 42 (1963), 21-27. (1963) Zbl0106.37103MR0146816
  19. Ore, O., 10.1007/BF02412090, Ann. Mat. Pura Appl., IV. Ser. 55 (1961), 315-321. (1961) Zbl0103.39702MR0162242DOI10.1007/BF02412090
  20. Zhou, B., Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl. 432 (2010), 566-570. (2010) Zbl1188.05086MR2577702

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.