Publications

Strongly spanning trailable graphs with short longest paths.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Ars Combinatoria
Year: 2018
Abstract: Let $G$ be a finite loopless graph. For $e\in E(G)$, let $v_e$ be a new vertex not contained in $V(G)$. For $e=u_1v_1$, $e'=u_2v_2\in E(G)$ (it is possible that $e=e'$), let $G(e,e')$ be the graph obtained from $G$ by replacing $e$ by a path $u_1v_ev_1$ and by replacing $e'$ by a path $u_2v_{e'}v_2$. $G$ is strongly spanning trailable if for any $e,e'\in E(G)$, $G(e,e')$ has a spanning $(v_e,v_{e'})$-trail. Note that strongly spanning trailable graphs are supereulerian. It is known that every 4-edge-connected graph is supereulerian [P.~A. Catlin, J. Graph Theory {\bf 12} (1988), no.~1, 29--44; [msn] MR0928734 [/msn]; F. Jaeger, J. Graph Theory {\bf 3} (1979), no.~1, 91--93; [msn] MR0519177 [/msn]]. W.~R. Pulleyblank [J. Graph Theory {\bf 3} (1979), no.~3, 309--310; [msn] MR0542555 [/msn]] indicated that determining whether a 3-edge-connected graph is supereulerian is NP-complete. In this paper, the authors investigate a sufficient condition for a 3-edge-connected graph to be strongly spanning trailable. \par Let $W_8$ be a graph such that $V(W_8)= \{w_0,w_1,w_2,w_3,w_4,w_5,w_6,w_7 \}$ and ${E(W_8)=\{w_iw_{i+1}:0\le i\le 7\}\cup\{w_iw_{i+4}:0\le i\le 3\}}$, where indices are modulo 8. The main theorem of the paper is the following: \par Let $G$ be a 3-edge-connected graph and $e,e'\in E(G)$ be edges. If the length of a longest $(v_e,v_{e'})$-path in $G(e,e')$ is at most 8, then either $G$ has a spanning $(v_e,v_{e'})$-trail, or ${G=W_8}$ with, up to isomorphism, $e=v_0v_4$ and $e'=v_2v_6$. \par As a corollary, the authors also show the following: \par Let $G$ be a 3-edge-connected graph. If for any edges $e,e'\in E(G)$, the length of a longest $(v_e,v_{e'})$-path in $G(e,e')$ is at most 8, then $G$ is strongly spanning trailable.
Link: Strongly spanning trailable graphs with short longest paths.