Spectral radius and Hamiltonicity of graphs with large minimum degree

被引:32
作者
Nikiforov, Vladimir [1 ]
机构
[1] Univ Memphis, Dept Math Sci, 3720 Alumni Ave, Memphis, TN 38152 USA
关键词
Hamiltonian cycle; Hamiltonian path; minimum degree; spectral radius;
D O I
10.1007/s10587-016-0301-y
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 aeyen 2, n aeyen k (3) + k + 4, and let G be a graph of order n, with minimum degree delta(G) aeyen k. If lambda(G) >= n - k - 1, then G has a Hamiltonian cycle, unless G = K V-1(K (n-k-1)+K (k) ) or G = K (k) V(K (n-2k) +(K) over bar (K) ).
引用
收藏
页码:925 / 940
页数:16
相关论文
共 21 条
  • [1] [Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
  • [2] [Anonymous], 1998, GRAD TEXT M
  • [3] [Anonymous], 1972, Journal of combinatorial theory, DOI DOI 10.1016/0095-8956(72)90020-2
  • [4] Spectral condition for Hamiltonicity of a graph
    Benediktovich, Vladimir I.
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 494 : 70 - 79
  • [5] METHOD IN GRAPH THEORY
    BONDY, JA
    CHVATAL, V
    [J]. DISCRETE MATHEMATICS, 1976, 15 (02) : 111 - 135
  • [6] Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian
    Butler, Steve
    Chung, Fan
    [J]. ANNALS OF COMBINATORICS, 2010, 13 (04) : 403 - 412
  • [7] Erd6s P., 1962, MAGYAR TUD AKAD MATH, V7, P227
  • [8] Fan Y.-Z., 2012, ARXIV12076824V1
  • [9] Spectral radius and Hamiltonicity of graphs
    Fiedler, Miroslav
    Nikiforov, Vladimir
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (09) : 2170 - 2173
  • [10] A sharp upper bound of the spectral radius of graphs
    Hong, Y
    Shu, JL
    Fang, KF
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 81 (02) : 177 - 183