Spanning Trails in a 2-Connected Graph
Abstract
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.
-
Every $2$-edge-connected graph of order at most 8 has a spanning trail starting from any vertex with the exception of six graphs.
-
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$.
- 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.