The Open UniversitySkip to content

Small vertex-transitive graphs of given degree and girth

Jajcay, Robert and Širáň, Jozef (2011). Small vertex-transitive graphs of given degree and girth. Ars Mathematica Contemporanea, 4(2) pp. 375–384.

Full text available as:
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (279Kb)
Google Scholar: Look up in Google Scholar


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.

Item Type: Journal Article
Copyright Holders: 2011 DMFA Slovenije
ISSN: 1855-3974
Keywords: vertex-transitive graph; cage; degree; girth
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 30422
Depositing User: Jozef Širáň
Date Deposited: 09 Dec 2011 10:27
Last Modified: 23 Feb 2016 20:40
Share this page:

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340