Hamiltonian Extendable Graphs

被引：0
作者：
Yang, Xiaojing [1 ]
Xiong, Liming [1 ]
机构：
[1] Beijing Inst Technol, Sch Math & Stat, Beijing Key Lab MCAACI, Beijing 100081, Peoples R China
来源：
DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2022年 / 42卷 / 03期
关键词：
Hamiltonian extendable; forbidden subgraph;
D O I：
10.7151/dmgt.2308
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.
引用
收藏
页码：843 / 859
页数：17
相关论文
共 15 条
[1]   On the Hamilton connectivity of generalized Petersen graphs [J].
Alspach, Brian ;
Liu, Jiping .
DISCRETE MATHEMATICS, 2009, 309 (17) :5461-5473
[2]   3-Connected {K 1,3, P 9}-Free Graphs are Hamiltonian-Connected [J].
Bian, Qiuju ;
Gould, Ronald J. ;
Horn, Paul ;
Janiszewski, Susan ;
La Fleur, Steven ;
Wrayno, Paul .
GRAPHS AND COMBINATORICS, 2014, 30 (05) :1099-1122
[3]  
Bondy J.A., 2008, GTM
[4]   Forbidden subgraphs that imply hamiltonian-connectedness [J].
Broersma, H ;
Faudree, RJ ;
Huck, A ;
Trommel, H ;
Veldman, HJ .
JOURNAL OF GRAPH THEORY, 2002, 40 (02) :104-119
[5]  
Chvatal V., 1972, Discrete Mathematics, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
[6]   Minimal graphs for matching extensions [J].
Costa, M. -C. ;
de Werra, D. ;
Picouleau, C. .
DISCRETE APPLIED MATHEMATICS, 2018, 234 :47-55
[7]  
Costa M.-C., EXTENSEURS HAMILTONI
[8]   Minimal graphs for 2-factor extension [J].
Costa, M-C ;
de Werra, D. ;
Picouleau, C. .
DISCRETE APPLIED MATHEMATICS, 2020, 282 :65-79
[9]   Characterizing forbidden pairs for Hamiltonian properties [J].
Faudree, RJ ;
Gould, RJ .
DISCRETE MATHEMATICS, 1997, 173 (1-3) :45-60
[10]   Generalization of matching extensions in graphs [J].
Liu, GZ ;
Yu, QL .
DISCRETE MATHEMATICS, 2001, 231 (1-3) :311-320
12