TY - JOUR
T1 - Spanning trails in a 2-connected graph
AU - Wang, Shipeng
AU - Xiong, Liming
N1 - Publisher Copyright:
© The authors.
PY - 2019
Y1 - 2019
N2 - In this article we prove the following: Let G be a 2-connected graph with cir- cumference c(G). If c(G) ≤ 5, then G has a spanning trail starting from any vertex, if c(G) ≤ 7, then G has a spanning trail. As applications of this result, we obtain the following. (1) Every 2-edge-connected graph of order at most 8 has a spanning trail starting from any vertex with the exception of six graphs. (2) Let G be a 2-edge-connected graph and S a subset of V (G) such that E(G - S) = θ and /S/ ≤ 6. Then G has a trail traversing all vertices of S with the exception of two graphs, moreover, if /S/ 6 4, then G has a trail starting from any vertex of S and containing S. (3) Every 2-connected claw-free graph G with order n and minimum degree δ(G) > n/7 + 4 ≥ 23 is traceable or belongs to two exceptional families of well-dened graphs, and moreover, if δ(G) > n/6 + 4 ≥ 13, then G is traceable. All above results are sharp in a sense.
AB - In this article we prove the following: Let G be a 2-connected graph with cir- cumference c(G). If c(G) ≤ 5, then G has a spanning trail starting from any vertex, if c(G) ≤ 7, then G has a spanning trail. As applications of this result, we obtain the following. (1) Every 2-edge-connected graph of order at most 8 has a spanning trail starting from any vertex with the exception of six graphs. (2) Let G be a 2-edge-connected graph and S a subset of V (G) such that E(G - S) = θ and /S/ ≤ 6. Then G has a trail traversing all vertices of S with the exception of two graphs, moreover, if /S/ 6 4, then G has a trail starting from any vertex of S and containing S. (3) Every 2-connected claw-free graph G with order n and minimum degree δ(G) > n/7 + 4 ≥ 23 is traceable or belongs to two exceptional families of well-dened graphs, and moreover, if δ(G) > n/6 + 4 ≥ 13, then G is traceable. All above results are sharp in a sense.
UR - http://www.scopus.com/inward/record.url?scp=85073631390&partnerID=8YFLogxK
U2 - 10.37236/8121
DO - 10.37236/8121
M3 - Article
AN - SCOPUS:85073631390
SN - 1077-8926
VL - 26
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 3
M1 - P3.56
ER -