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


Extremal Regular Graphs with Prescribed Odd Girth
Authors:Zhang G. H.
Abstract:The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ƒ(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ƒ(k, g) ≥ kg/2 and that ƒ(k, g) = kg/2 if k is even. The exact values of ƒ(k, g) are also known if k = 3 or g = 5. Let xe denote the smallest even integer no less than x, δ(g) = (−1)g − 1/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ≥ 5 and g ≥ 7 are both odd, then [formula] with the exception that ƒ(5, 7) = 20.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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