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


On the maximum number of diagonals of a circuit in a graph
Authors:Ram Prakash Gupta  Jeff Kahn  Neil Robertson
Institution:Department of Mathematics, Ohio State University, 231 West 18th Avenue, Columbus, OH 43210, USA
Abstract:For a graph G, let ?(G) denote the maximum number k such that G contains a circuit with k diagonals.Theorem. For any graph G with minimum valencyn? 3, ?(G) ? 12 (n+1)(n-2).If the equality holds and G is connected, then either G is isomorphic to Kn+1 or G is separable and each of its terminal blocks is isomorphic to Kn+1, or Kn+1 with one edge subdivided.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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