2024/11/14 by Goedgebeur, Jan, Mattiolo, Davide, Mazzuoccolo, Giuseppe +3 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2411.09806
A recent result by Kardoš, Máčajová and Zerafa [J. Comb. Theory, Ser. B. 160 (2023) 1--14] related to the famous Berge-Fulkerson conjecture implies that given an arbitrary set of odd pairwise edge-disjoint cycles, say \mathcal O, in a bridgeless cubic graph, there exists a 1-factor intersecting all cycles in \mathcal O in at least one edge. This remarkable result opens up natural generalizations in the case of an r-regular graph G and a t-factor F, with r and t being positive integers. In this paper, we start the study of this problem by proving necessary and sufficient conditions on G, t and r to assure the existence of a suitable F for any possible choice of the set \mathcal O. First of all, we show that G needs to be 2-connected. Under this additional assumption, we highlight how the ratio (t)/(r) seems to play a crucial role in assuring the existence of a t-factor F with the required properties by proving that (t)/(r) ≥ (1)/(3) is a further necessary condition. We suspect that this condition is also sufficient, and we confirm it in the case (t)/(r)=(1)/(3), generalizing the case t=1 and r=3 proved by Kardoš, Máčajová, Zerafa, and in the case (t)/(r)=(1)/(2) with t even. Finally, we provide further results in the case of cycles of arbitrary length.