Small vertex-transitive graphs of given degree and girth
DOI:
https://doi.org/10.26493/1855-3974.124.06dKeywords:
vertex-transitive graph, cage, degree, girthAbstract
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.Downloads
Published
2011-09-12
Issue
Section
GEMS 2009 - Tale, Slovakia
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/