Hoffman-Singleton Decomposition of K50


Definitions: The Hoffman-Singleton graph [HS] is a 7-regular graph with girth 5 on 50 vertices. It is the only such graph with the fewest vertices, which makes it the unique (7,5)-cage. (Other proofs of uniqueness appear in [FS, OW].) The graph consists of ten 5-cycles P0,...,P4 and Q0,...,Q4, each with vertices modulo 5, and vertex i of Pj adjacent to vertex i+jk (mod 5) of Qk.

Question: Does K50 decompose into 7 copies of the Hoffman-Singleton graph?

Comments/Partial results: Meszka and Siagiova [MS] have found five edge-disjoint copies of the Hoffman-Singleton graph in K50, using voltage graph methods.

[FS] Fan, C.; Schwenk, A. J. Structure of the Hoffman-Singleton graph. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 94 (1993), 3--8.
[HS] Hoffman, A. J.; Singleton, R. R. On Moore graphs with diameters 2 and 3. IBM J. Res. Develop. 4 1960 497--504.
[MS] Meszka, M.; Siagiova, J. A covering construction for packing disjoint copies of the Hoffman-Singleton graph into K50. J. Combinatorial Designs, to appear.
[OW] O'Keefe, M.; Wong, P. K. On certain regular graphs of girth 5. Internat. J. Math. Math. Sci. 7 (1984), no. 4, 785--791.

Back to Index Page Link to Glossary