A Shrikhande challenge

I discussed here the problem of covering the m-fold complete graph on n vertices with copies of a given graph G.

The smallest strongly regular graph for which I don’t know the answer is the Shrikhande graph. I can copy 8.K16 with 20 copies of the Shrikhande graph, but perhaps one can do better.

Problem: Is it possible to cover 2.K16 with five copies of the Shrikhande graph? I count all the things that need to be counted.
This entry was posted in open problems and tagged . Bookmark the permalink.

1 Response to A Shrikhande challenge

1. Peter Cameron says:

Darryn Bryant has solved the Shrikhande challenge. He writes: Here is the Shrikhande graph. Now, if you take the five images of this graph under powers of the permutation (X)(0 3  6 9 12)(1 4 7 10 13)(2 5 8 11 14), you cover the edges of the complete graph twice, as required.

Darryn also points out that Ben Fairbairn’s question has been answered in a paper by Peter Adams, Darryn E. Bryant and A. Khodkar, The spectrum problem for lambda-fold Petersen graph designs, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 159-176. The answer is, mKn can always be partitioned into Petersen graphs as long as n is at least 10 and the obvious divisibility conditions (3 divides m(n−1) and 15 divides mn(n−1)/2) are satisfied, except for the single case m=1, n=10.

This site uses Akismet to reduce spam. Learn how your comment data is processed.