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


The ratio of the numbers of odd and even cycles in outerplanar graphs
Institution:1. Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Suita, Osaka 565-0871, Japan;2. Research Institute for Digital Media and Content, Keio University, Yokohama, Kanagawa 232-0062, Japan
Abstract:In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.
Keywords:Enumeration  Outerplanar graph  Cycle  Subtree  Claw-free
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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