Spanning trails in a 2-connected graph

Shipeng Wang, Liming Xiong

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article numberP3.56
JournalElectronic Journal of Combinatorics
Volume26
Issue number3
DOIs
Publication statusPublished - 2019

Fingerprint

Dive into the research topics of 'Spanning trails in a 2-connected graph'. Together they form a unique fingerprint.

Cite this