Geodesic
Spectral radius and Hamiltonicity of graphs with large minimum degree
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 925-940
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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}).$
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}).$
DOI : 10.1007/s10587-016-0301-y
Classification : 05C35, 05C50
Keywords: Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius 
@article{10_1007_s10587_016_0301_y,
     author = {Nikiforov, Vladimir},
     title = {Spectral radius and {Hamiltonicity} of graphs with large minimum degree},
     journal = {Czechoslovak Mathematical Journal},
     pages = {925--940},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0301-y},
     mrnumber = {3556876},
     zbl = {06644042},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0301-y/}
}
TY  - JOUR
AU  - Nikiforov, Vladimir
TI  - Spectral radius and Hamiltonicity of graphs with large minimum degree
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 925
EP  - 940
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0301-y/
DO  - 10.1007/s10587-016-0301-y
LA  - en
ID  - 10_1007_s10587_016_0301_y
ER  - 
%0 Journal Article
%A Nikiforov, Vladimir
%T Spectral radius and Hamiltonicity of graphs with large minimum degree
%J Czechoslovak Mathematical Journal
%D 2016
%P 925-940
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0301-y/
%R 10.1007/s10587-016-0301-y
%G en
%F 10_1007_s10587_016_0301_y
Nikiforov, Vladimir. Spectral radius and Hamiltonicity of graphs with large minimum degree. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 925-940. doi: 10.1007/s10587-016-0301-y

[1] Benediktovich, V. I.: Spectral condition for Hamiltonicity of a graph. Linear Algebra Appl. 494 (2016), 70-79. | MR | Zbl

[2] Bollob{á}s, B.: Modern Graph Theory. Graduate Texts in Mathematics 184 Springer, New York (1998). | MR | Zbl

[3] Bondy, J. A., Chvátal, V.: A method in graph theory. Discrete Math. 15 (1976), 111-135. | DOI | MR | Zbl

[4] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Ann. Comb. 13 (2010), 403-412. | DOI | MR | Zbl

[5] Chv{á}tal, V.: On Hamilton's ideals. J. Comb. Theory, Ser. B 12 (1972), 163-168. | DOI | Zbl

[6] Dirac, G. A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc., III. Ser. 2 (1952), 69-81. | DOI | MR | Zbl

[7] Erd{ő}s, P.: Remarks on a paper of Pósa. Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7 (1962), 227-229. | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[11] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42 (2003), 17-33. | DOI | MR | Zbl

[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 | Zbl

[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 | MR

[14] Liu, R., Shiu, W. C., Xue, J.: Sufficient spectral conditions on Hamiltonian and traceable graphs. Linear Algebra Appl. 467 (2015), 254-266. | MR | Zbl

[15] Lu, M., Liu, H., Tian, F.: Spectral radius and Hamiltonian graphs. Linear Algebra Appl. 437 (2012), 1670-1674. | MR | Zbl

[16] Nikiforov, V.: Some inequalities for the largest eigenvalue of a graph. Comb. Probab. Comput. 11 (2002), 179-189. | DOI | MR | Zbl

[17] Ning, B., Ge, J.: Spectral radius and Hamiltonian properties of graphs. Linear Multilinear Algebra 63 (2015), 1520-1530. | DOI | MR | Zbl

[18] Ore, O.: Hamilton connected graphs. J. Math. Pures Appl., IX. Sér. 42 (1963), 21-27. | MR | Zbl

[19] Ore, O.: Arc coverings of graphs. Ann. Mat. Pura Appl., IV. Ser. 55 (1961), 315-321. | DOI | MR | Zbl

[20] Zhou, B.: Signless Laplacian spectral radius and Hamiltonicity. Linear Algebra Appl. 432 (2010), 566-570. | MR | Zbl

Cité par Sources :