2025/08/06 by Fujisawa, Jun
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.04507
Let m and r be integers with m ≥ r ≥ 3 and let G be an r-regular graph of even order. Let M be a matching in G of size m such that each pair of edges in M is at distance at least 3. In 2023, Aldred et al. proved that if G is cyclically (mr-r+1)-edge-connected and G is bipartite, then there exists a perfect matching of G containing M. In this paper, we present non-bipartite analogues of Aldred et al.'s theorem. An odd ear of U ⊆ V(G) is a path of odd length whose ends lie in U but whose internal vertices do not, or a cycle of odd length having exactly one vertex in U. Our first result shows that if G is cyclically (mr - m +1)-edge-connected and there exist mr - \lceil (r)/(2) \rceil + 1 edge-disjoint odd ears of V(M), then M can be extended to a perfect matching of G. We further show that if G contains mr-r+1 edge-disjoint odd ears of V(M) and no cyclic edge cut in G of size less than (2m-1)(r-1) separates an odd cycle from another cycle, then M can still be extended to a perfect matching. The second result extends Aldred et al.'s theorem to non-bipartite graphs in the case r ≥ 4, and in the case when r = 3 and each pair of edges in M is at distance at least 5. It is also shown that the above results hold when m ≤ r - 1, without assuming the distance condition on M.