Spanning Trails in a 2-Connected Graph

  • Shipeng Wang
  • Liming Xiong


In this article we prove the following: Let $G$ be a $2$-connected graph with circumference $c(G)$. If  $c(G)\leq 5$, then $G$ has a spanning trail starting from any vertex, if  $c(G)\leq 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)=\emptyset$ and $|S|\leq 6$. Then $G$ has a trail traversing all vertices of $S$ with the exception of two graphs, moreover, if $|S|\leq 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 $\delta(G)> \frac{n}{7}+4\geq 23$ is traceable or belongs to two exceptional families of well-defined  graphs, and moreover, if $\delta(G)> \frac{n}{6}+4\geq 13$, then $G$ is traceable.

All above results are sharp in a sense.

Article Number