Robert Jajcay (Indiana State Universtity, ZDA): Small vertex-transitive graphs of given degree and girth

Datum objave: 16. 11. 2009
Seminar za teorijo grup in kombinatoriko
Četrtek, 19. 11. 2009, od 17h do 19h, učilnica 016, Pedagoška fakulteta Univerze v Ljubljani
Povzetek: We investigate the basic interplay between the small k-valent vertex-transitive graphs of girth g and the (k,g)-cages, the smallest k-valent graphs of girth g. We prove the existence of k-valent Cayley graphs of girth g for every pair of parameters k \geq 2 and g \geq 3, improve the lower bounds on the order of the smallest (k,g) vertex-transitive graphs for certain families of odd girth, and generalize the construction of Bray, Parker and Rowley that has yielded several of the smallest known (k,g)-graphs.