4
$\begingroup$

Three copies of the Clebsch Graph can cover $K_{16}$, the complete graph on 16 vertices. This is part of the demonstration that $\mathrm{Ramsey}(3,3,3) > 16$.

Clebsch 3-cover of K_16

The Hoffman–Singleton graph is a (7,5)-cage, and is one of the more famous graphs in graph theory. Can 7 copies of this graph cover the complete graph $K_{50}$?

1 Answers 1

2

This is quite a curious question, but it seems to be an open problem. I found a discussion of it here:

Jana Ŝiagiová, Mariusz Meszka, A covering construction for packing disjoint copies of the Hoffman-Singleton graph into K50, J. Combin. Des. 11 (2003), no. 6, 408–412.

A complete solution seems to be difficult to obtain; nevertheless we show a construction of packing of five Hoffman-Singleton graphs into K50 using the covering method.

and elsewhere in the paper

The question whether more than five copies of the Hoffman-Singleton graph can be packed into K50 still remains open.