# Has this distance-2 $K_k$-factor problem been studied before?

Let $$G=(V,E)$$ be a finite simple graph. For any positive integer $$k \geq 1$$, a distance-2 $$K_k$$-factor is a collection of cliques $$K_k$$ of $$G$$ such that for every two vertices $$u$$ and $$v$$ in distinct members of the collection, the distance between $$u$$ and $$v$$ is at least two.

For $$k = 1$$, this is known as a distance-2 independent set. For $$k = 2$$, this is known as an induced matching (also known as a strong matching). These are known concepts that have definitely been studied before.

But has the problem been studied for larger $$k$$, particularly $$k=3$$, before? Does it have a more familiar name?

• For what it's worth, 'packing' is generally used to indicate that you want edge-disjoint copies, not vertex-disjoint; 'K_k-factor' or 'K_k-matching' would be more like the usual terms. But, I have not seen this particular problem studied. It might help to know more about what you want: are you interested in the number of K_ks being fixed, or growing..? Extremal conditions of some kind (obviously, not anything too standard as it's not monotone) or more structural? – user36212 May 1 at 21:10
• @user36212 Thanks! What I'm most interested in at the moment is $k=3$ fixed and the maximum size of such a $K_k$-factor in a connected 4-regular graph. This could be contrasted with the case of $k=2$, where (IIRC) a connected cubic graph of size $m$ is known to have strong matching number of at least $m/9$. – Juho May 2 at 6:09