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?


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged . Bookmark the permalink.

One Response to A Shrikhande challenge

  1. Darryn Bryant has solved the Shrikhande challenge. He writes:

    Shrikhande graph

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s