# Efficient way to get all $k$-factors of a graph $G$?

In Graph factorization, a $$k$$-factor of a graph $$G$$ is a spanning $$k$$-regular subgraph which has the same vertex set as $$G$$. Now I have a random graph $$g$$ (i.e. complete graph for simplicity) and I want to obtain all the $$k$$-factors in a list.

My strategy is

1. get the edges and vertex of $$G$$: getpairs and getvetex
2. create all the subsets of getpairs: allsublist, which is equivalent to create all the possible subgraphs.
• check whether each elements (i.e. number) in every subset is repeated $$k$$ times (i.e. terms), which corresponds to check every subgraph is $$k$$-regular graph.
• check each terms have the same vertex set getvetex of $$G$$
3. store the correct subsets (i.e. $$k$$-factors) in selectlists.
4. repeat steps 3-4 (namely the for-loop)

Here is the code for the above task:

n = 5;
g= CompleteGraph[n];
getpairs = EdgeList[g] /. UndirectedEdge -> List;
getvetex = VertexList[g];

selectlists = {};
kregular = 2;
allsublist = Subsets[getpairs];
For[ii = 1, ii <= Length[allsublist], ii++,
terms = Cases[Tally@Flatten@allsublist[[ii]], {x_, kregular} :> x];
If[terms!={} && terms==DeleteDuplicates@Flatten@allsublist[[ii]] && SameQ[SortBy[terms,Greater],getvetex],
AppendTo[selectlists, allsublist[[ii]]];];
];


For-Loop is quite inefficient and create all Subsets will also take long time when there are many edges in the graph with large n.

Let's say n currently is small n<=6, can one get rid of the for-loop? Are there simple ways to do it? Thank you very much in advance!

• How large do you expect your graphs to be? In general you want to avoid loops in Mathematica, but for something like $n=20$, you have $2^{190}$ subsets which is not going to be feasible and may need a procedural approach. Also, how do you feel about isomorphic graphs? May be able to reduce the computation if we can ignore isomorphic graphs. Jul 23 at 15:54
• Let's say the graph currently is limited to n<=6? if we current ignore the large n case, get rid of for-loops can still somehow speed up a bit? @bRost03 Jul 23 at 16:05

One big speed-up you can get is realizing a $$k$$-regular graph has $$kn/2$$ edges so you don't have to generate all subsets of the edges. This goes from considering $$2^{n(n-1)/2}$$ subsets to $$\binom{n (n-1) /2}{kn/2}$$ which is a large savings. I am still thinking if there's a way to get more savings by constraints involving spanning sets or regular sets. Either way, here's a more functional solution as opposed to your procedural one. For $$n=7$$, $$k=2$$ this is 30x faster than your code on my machine.

edges[n_] := EdgeList@CompleteGraph[n];
kEdges[k_, n_] := If[OddQ[k n], Print["No k-factors"]; Abort[];,
Subsets[edges[n], {k n/2}]]
regularSpanQ[edges_, k_] := Equal @@ Append[Last@Thread[Tally@Flatten[List @@@ edges]], k]


then for example

With[{k = 2, n = 6}, Graph /@ Select[kEdges[k, n], regularSpanQ[#, k] &]]


gives • thank you very much! It's a really good point that one can reduce the Subsets with some conditions. Jul 23 at 16:20
• just one question, will the method ( i.e. Subsets[edgeslist, {k n/2}]]) work for non-complete graph such as PetersenGraph[5,1] (although many vertices but few edges)? @bRost03 Jul 24 at 7:59
• Yes, that condition is from the fact that your $k$-factor is $k$-regular and has nothing to do with the underlying graph Jul 24 at 11:31
• the condition n is the number of vertex, right? Jul 24 at 14:37
• @Xuemei Correct Jul 24 at 14:47