Spanning path-cycle systems with given end-vertices in regular graphs (full version)

Abstract

We prove the following theorem. Let $r\ge 4$ be an integer, and $G$ be a $K_{1,r}$-free $r$-edge-connected $r$-regular graph. Then, for every set $W$ of even number of vertices of $G$ such that the distance between any two vertices of $W$ in $G$ is at least 3, $G$ has vertex-disjoint paths and cycles $P_1,\dots ,P_m,C_1,\dots ,C_n$ such that (i) $V(G)=V(P_1)\cup \cdots \cup V(P_m)\cup V(C_1)\cup \cdots \cup V(C_n)$, (ii) each path $P_i$ connects two vertices of $W$, and (iii) the set of the end-vertices of $P_i$'s is equal to $W$. A similar result for a 3-regular graph is obtained in [Graphs Combin. {\bf 39} (2023) \#85]. However, our proof is widely different from its proof.

19 pages, 9 figures