Primož Šparl (Pef UL, Slovenija): On extendability of Cayley graphs

Datum objave: 12. 10. 2009
Seminar za teorijo grup in kombinatoriko
Četrtek, 15. 10. 2009, od 17h do 19h, učilnica 016, Pedagoška fakulteta Univerze v Ljubljani

Abstract: A connected graph \Gamma of even order is n-extendable, if it contains a matching of size n and if every such matching is contained in a perfect matching of \Gamma. Furthermore, a connected graph \Gamma of odd order is n\frac{1}{2}-extendable, if for every vertex v of \Gamma the graph \Gamma - v is n-extendable.

We discuss some of the known results on n-extendability and n\frac{1}{2}-extendability. We then prove that every connected Cayley graph of an abelian group of odd order which is not a cycle is
1\frac{1}{2}-extendable. Using this result we then obtain a classification of 2-extendable connected Cayley graphs of generalized dihedral groups.