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:
[img]
Preview
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (279Kb)
URL: http://amc-journal.eu/index.php/amc/article/view/1...
Google Scholar: Look up in Google Scholar

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.

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
Item ID: 30422
Depositing User: Jozef Širáň
Date Deposited: 09 Dec 2011 10:27
Last Modified: 17 Jul 2014 02:30
URI: http://oro.open.ac.uk/id/eprint/30422
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk