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 -