Extremal problems on distance spectra of graphs

被引:10
作者
Lin, Huiqiu [1 ]
Zhang, Yuke [1 ]
机构
[1] East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China
基金
中国国家自然科学基金;
关键词
Distance spectral radius; The sum of eigenvalues; Hamilton cycle; Hamilton path;
D O I
10.1016/j.dam.2020.09.023
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Motivated by recent progresses on spectral extremal graph theory, in this paper, we aim to investigate the existence of cycles with given length in a graph in terms of its distance spectral radius. First of all, we show that if G is a connected bipartite graph with lambda(1) (D(G)) <= lambda(1)(D(K-1,(n-1))), then G contains a C-4 unless G congruent to K-1,(n-1). When n is sufficiently large with respect to k, as a corollary, we show that S-k(D(G)) >= 2n - 2k if G is a C-4-free bipartite graph. Besides, we prove that S-k(D(G)) >= 2n - 2k if G is a bipartite distance regular graph. These two results partially solve a problem proposed by Lin (2019). Secondly, we give sufficient conditions for the existence of a Hamilton cycle or Hamilton path in a balanced bipartite graph in terms of the distance spectral radius. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码:139 / 147
页数:9
相关论文
共 20 条
[1]   Proximity, remoteness and distance eigenvalues of a graph [J].
Aouchiche, Mustapha ;
Hansen, Pierre .
DISCRETE APPLIED MATHEMATICS, 2016, 213 :17-25
[2]   Distance spectra of graphs: A survey [J].
Aouchiche, Mustapha ;
Hansen, Pierre .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 458 :301-386
[3]   METHOD IN GRAPH THEORY [J].
BONDY, JA ;
CHVATAL, V .
DISCRETE MATHEMATICS, 1976, 15 (02) :111-135
[4]   Wiener index, Harary index and graph properties [J].
Feng, Lihua ;
Zhu, Xiaomin ;
Liu, Weijun .
DISCRETE APPLIED MATHEMATICS, 2017, 223 :72-83
[5]  
Füredi Z, 2013, BOLYAI SOC MATH STUD, V25, P169
[6]  
KOVARI T, 1954, C MATH, V3, P50
[7]   Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs [J].
Li, Binlong ;
Ning, Bo .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 515 :180-195
[8]   Spectral analogues of Erdos' and Moon-Moser's theorems on Hamilton cycles [J].
Li, Binlong ;
Ning, Bo .
LINEAR & MULTILINEAR ALGEBRA, 2016, 64 (11) :2252-2269
[9]   On the sum of k largest distance eigenvalues of graphs [J].
Lin, Huiqiu .
DISCRETE APPLIED MATHEMATICS, 2019, 259 :153-159
[10]   Remoteness and distance eigenvalues of a graph [J].
Lin, Huiqiu ;
Das, Kinkar Ch. ;
Wu, Baoyindureng .
DISCRETE APPLIED MATHEMATICS, 2016, 215 :218-224