Spectral radius and Hamiltonicity of graphs with large minimum degree
Czechoslovak Mathematical Journal (2016)
- Volume: 66, Issue: 3, page 925-940
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topNikiforov, 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- Benediktovich, V. I., Spectral condition for Hamiltonicity of a graph, Linear Algebra Appl. 494 (2016), 70-79. (2016) Zbl1331.05125MR3455686
- Bollob{á}s, B., Modern Graph Theory, Graduate Texts in Mathematics 184 Springer, New York (1998). (1998) Zbl0902.05016MR1633290
- 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
- Butler, S., Chung, F., 10.1007/s00026-009-0039-4, Ann. Comb. 13 (2010), 403-412. (2010) Zbl1229.05193MR2581094DOI10.1007/s00026-009-0039-4
- 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
- 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
- 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
- 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)
- 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
- 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
- Krivelevich, M., Sudakov, B., 10.1002/jgt.10065, J. Graph Theory 42 (2003), 17-33. (2003) Zbl1028.05059MR1943104DOI10.1002/jgt.10065
- 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
- Li, B., Ning, B., 10.1080/03081087.2016.1151854, Linear Multilinear Algebra DOI:10.1080/03081087.2016.1151854. MR3539577DOI10.1080/03081087.2016.1151854
- 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
- Lu, M., Liu, H., Tian, F., Spectral radius and Hamiltonian graphs, Linear Algebra Appl. 437 (2012), 1670-1674. (2012) Zbl1247.05129MR2946350
- Nikiforov, V., 10.1017/S0963548301004928, Comb. Probab. Comput. 11 (2002), 179-189. (2002) Zbl1005.05029MR1888908DOI10.1017/S0963548301004928
- Ning, B., Ge, J., 10.1080/03081087.2014.947984, Linear Multilinear Algebra 63 (2015), 1520-1530. (2015) Zbl1332.05091MR3304990DOI10.1080/03081087.2014.947984
- Ore, O., Hamilton connected graphs, J. Math. Pures Appl., IX. Sér. 42 (1963), 21-27. (1963) Zbl0106.37103MR0146816
- Ore, O., 10.1007/BF02412090, Ann. Mat. Pura Appl., IV. Ser. 55 (1961), 315-321. (1961) Zbl0103.39702MR0162242DOI10.1007/BF02412090
- Zhou, B., Signless Laplacian spectral radius and Hamiltonicity, Linear Algebra Appl. 432 (2010), 566-570. (2010) Zbl1188.05086MR2577702
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.