A Note on Singular Edges and Hamiltonicity in Claw-Free Graphs with Locally Disconnected Vertices

被引:0
作者
Ryjacek, Zdenek [1 ]
Vrana, Petr [1 ]
Xiong, Liming [2 ]
机构
[1] Univ West Bohemia, NTIS, European Ctr Excellence, Dept Math, Univ 8, Plzen, Czech Republic
[2] Beijing Inst Technol, Beijing Key Lab MCAACI, Sch Math & Stat, Beijing 100081, Peoples R China
关键词
Claw-free graph; Hamiltonian graph; Singular edge; Locally disconnected vertex; Closure; Contractible subgraph; CIRCUITS;
D O I
10.1007/s00373-020-02144-1
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An edge e of a graph G is called singular if it is not on a triangle; otherwise, e is nonsingular. A vertex is called singular if it is adjacent to a singular edge; otherwise, it is called nonsingular. We prove the following. Let G be a connected claw-free graph such that every locally disconnected vertex x is an element of V(G) satisfies the following conditions: (i) if x is nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 4 nonsingular edges, (ii) if x is not nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 3 nonsingular edges, (iii) if x is of degree 2, then x is singular and x is on an induced cycle C of length at least 4 with at most 2 nonsingular edges such that G[V(C)boolean AND V2(G)] is a path or a cycle. Then G is either hamiltonian, or G is the line graph of the graph obtained from K2,3by attaching a pendant edge to its each vertex of degree two. Some results on forbidden subgraph conditions for hamiltonicity in 3-connected claw-free graphs are also obtained as immediate corollaries
引用
收藏
页码:665 / 677
页数:13
相关论文
共 13 条
[1]   Sufficient condition for Hamiltonicity of N2-locally connected claw-free graphs [J].
Bielak, H .
DISCRETE MATHEMATICS, 2000, 213 (1-3) :21-24
[2]  
Bondy J. A, 2008, GRAPH THEORY
[3]   A REDUCTION METHOD TO FIND SPANNING EULERIAN SUBGRAPHS [J].
CATLIN, PA .
JOURNAL OF GRAPH THEORY, 1988, 12 (01) :29-44
[4]   Forbidden Subgraphs for Hamiltonicity of 3-Connected Claw-Free Graphs [J].
Fujisawa, Jun .
JOURNAL OF GRAPH THEORY, 2013, 73 (02) :146-160
[5]  
Harary F., 1965, CANAD MATH B, V8, P701, DOI DOI 10.4153/CMB-1965-051-3
[6]  
Li MC, 2002, ARS COMBINATORIA, V62, P281
[7]   EVERY CONNECTED, LOCALLY CONNECTED NONTRIVIAL GRAPH WITH NO INDUCED CLAW IS HAMILTONIAN [J].
OBERLY, DJ ;
SUMNER, DP .
JOURNAL OF GRAPH THEORY, 1979, 3 (04) :351-356
[8]   Contractibility techniques as a closure concept [J].
Ryjácek, Z ;
Schelp, RH .
JOURNAL OF GRAPH THEORY, 2003, 43 (01) :37-48
[9]   On a closure concept in claw-free graphs [J].
Ryjacek, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :217-224
[10]   HAMILTONIAN CIRCUITS IN N2-LOCALLY CONNECTED K1,3-FREE GRAPHS [J].
RYJACEK, Z .
JOURNAL OF GRAPH THEORY, 1990, 14 (03) :321-331