Seminar of Theoretical Computer Science - Martin Mačaj (19.10.2018)

Friday 19.10.2018 at 11:00, Lecture room M/213

15. 10. 2018 09.32 hod.
By: Rastislav Královič

Martin Mačaj:
On packings of disjoint copies of the Petersen and the Hoffman-Singleton graphs into complete graphs

Abstract:
In 1983, A.J. Schwenk asked whether it is possible to decompose K_10 into three copies of the Petersen graph. In an analogous way, we may ask whether there exists a decomposition of K_50 into seven copies of the Hoffman-Singleton graph (HoSi).
In this talk, we consider the above problems from the computational point of view. First, we recall the answer to the first question. Then, we introduce the Hoffman-Singleton graph and its relation to the Petersen graph. Using methods of J. Šiagiová and M. Meszka, we answer the second question under the condition that all HoSis share a non-trivial automorphism. Finally, we pose some open problems.

A.J. Schwenk, Advanced problem 6434, Amer. Math. Monthly 90(1983) 403.
J. Šiagiová, M. Meszka, A covering construction for packing disjoint copies of the Hoffman-Singleton graph into K_50, J. Combin. Des. 11 (2003) 408--412

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php