3
$\begingroup$

The following exercise problem is from the book of D.B.West which i could solve:

If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.

So my questions are the following,

  1. If a complete graph of $n$ vertices can be decomposed into cliques of size $p$ with $p\leq n$ then what should be the relation between $n$ and $p$.

  2. What is the official name of this problem in the literature ?

Any links/hints would be helpful.

$\endgroup$
12
$\begingroup$

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://steinertriples.fr/

If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are "Balanced Incomplete Block Designs". If you want to know more about that, try to find the book from Douglas Stinson named "Combinatorial designs: construction and analysis".

Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a (v,k,1)-BIBD whenever one exists for k<=5, and as for larger values of k, well, it depends.

Either way, if you find a combinatorial design that it cannot build come tell us about it ! :-P

Nathann

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The reference to the book indeed helped. $\endgroup$ – Dibyayan Sep 8 '14 at 5:24
0
$\begingroup$

I think if the size of clique, i.e. $p$ is prime, then the following statement is true.

If a complete graph of $n$ vertices can be decomposed into cliques of size p with $p≤n$ then $n-1$ or $n-p$ is divided by $p(p-1)$.

The above statement also holds if $p=2^k$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.