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?

  • $\begingroup$ 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? $\endgroup$ – user36212 May 1 at 21:10
  • $\begingroup$ @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$. $\endgroup$ – Juho May 2 at 6:09

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.