Small vertex-transitive graphs of given degree and girth

Robert Jajcay, Jozef Širáň

Abstract


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 pairof parameters k ≥ 2 and g ≥ 3, improve the lower bounds on the order of the smallest (k, g) vertex-transitive graphs forcertain families with prime power girth, and generalize the construction of Bray, Parker and Rowley that has yielded several of the smallest known (k, g)-graphs.

Keywords


vertex-transitive graph; cage; degree; girth

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.124.06d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications