2025/08/15 by Egawa, Yoshimi, Kano, Mikio, Ozeki, Kenta · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.11302
We prove the following theorem. Let r≥ 4 be an integer, and G be a K1,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 P1, …, Pm, C1, …, Cn such that (i) V(G)=V(P1) ∪ ⋯ ∪ V(Pm) ∪ V(C1) ∪ ⋯ ∪ V(Cn), (ii) each path Pi connects two vertices of W, and (iii) the set of the end-vertices of Pi'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.