Article ID Journal Published Year Pages File Type
8903087 Discrete Mathematics 2018 9 Pages PDF
Abstract
We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive k-regular graphs of girth g. Counting cycles to obtain necessary arithmetic conditions on the parameters (k,g), we extend previous results of Biggs, and prove that, for any given excess e and any given degree k≥4, the asymptotic density of the set of girths g for which there exists a vertex-transitive (k,g)-cage with excess not exceeding e is 0.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,