首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 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 k4, 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.
Keywords:Cage problem  Vertex-transitive graph  Lower bound  Degree  Girth
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号