Seminár z teoretickej informatiky - Martin Mačaj (19.10.2018)

v piatok 19.10.2018 o 11:00 hod. v miestnosti M/213

---

Prednášajúci:  Martin Mačaj

Názov:  On packings of disjoint copies of the Petersen and the Hoffman-Singleton graphs into complete graphs

Termín:  19.10.2018, 11:00 hod., M/213

Abstrakt:
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

---