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 (285kB)
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: Article
Copyright Holders: 2011 DMFA Slovenije
ISSN: 1855-3974
Keywords: vertex-transitive graph; cage; degree; girth
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 30422
Depositing User: Jozef Širáň
Date Deposited: 09 Dec 2011 10:27
Last Modified: 04 Oct 2016 22:27
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

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