The ratio of the numbers of odd and even cycles in outerplanar graphs |
| |
Affiliation: | 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 等数据库收录! |
|