Given a graph $G$, if we can partition the edges into pairwise disjoint subsets of $G$, such that the union of all the subsets is equal to the edgeset of G, then this is a decomposition. If such a partition can be formed from only spanning k-regular graphs, where all the graphs are disjoint, then each of these graphs is a k-factor, and the graph is k-factorizable. If a graph is 2-factorizable, then what conditions are nessasary to make the connected components of each 2-factor the same length?

Related to this recent question

  • $\begingroup$ All the factors are of equal size by definition. Do you mean to ask when the components of the factors are of equal size? $\endgroup$ – Brendan McKay Mar 5 '16 at 9:58
  • $\begingroup$ I may just not understand what a factor is, then. Why are they of equal size? I suspect the question you proposed is what I meant to ask, and I just don't know it. $\endgroup$ – Juan Sebastian Lozano Mar 5 '16 at 10:02
  • $\begingroup$ A 2-factor is a spanning 2-regular subgraph. So if the whole graph has $n$ vertices, a 2-factor has $n$ vertices and $n$ edges. Perhaps you are just trying to decompose the edge set into cycles? $\endgroup$ – Brendan McKay Mar 5 '16 at 10:08
  • $\begingroup$ You are correct, and this question makes no sense in light of that. However, what is the difference between a two factor and a two factorization? But yes, that is exactly what I am trying to do, I am looking for cycles which are of equal length in the graph. $\endgroup$ – Juan Sebastian Lozano Mar 5 '16 at 10:12
  • 1
    $\begingroup$ A 2-factorization is a partition of the edge set into 2-factors. Go to Google Scholar and search for "graph cycle decomposition". There are lots of partial results but no complete answer. You should do such searches before asking a question here. $\endgroup$ – Brendan McKay Mar 5 '16 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.