On the excess of vertex-transitive graphs of given degree and girth |
| |
Authors: | Slobodan Filipovski Robert Jajcay |
| |
Institution: | 1. University of Primorska, Koper, Slovenia;2. Comenius University, Bratislava, Slovakia |
| |
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 -regular graphs of girth . Counting cycles to obtain necessary arithmetic conditions on the parameters , we extend previous results of Biggs, and prove that, for any given excess and any given degree , the asymptotic density of the set of girths for which there exists a vertex-transitive -cage with excess not exceeding is 0. |
| |
Keywords: | Cage problem Vertex-transitive graph Lower bound Degree Girth |
本文献已被 ScienceDirect 等数据库收录! |
|