Estimating the number of short cycles in simple planar graphs
-
摘要: 证明一个\,$n$\,阶简单\,$2$-连通平面图\,$G$\,中至多有\,$O(n^{2})$\,个最短圈\,(即存在绝对常数\,$c0$\,使得\,$G$\,中至多有\,$cn^2$\,个最短圈), 且该界就\,$n$\,的量级来讲是最好可能的, $K_{n-2,2}$\,表明了\,$n^2$\,是可以达到的量级.
-
关键词:
- 短圈 /
- 基本圈 /
- Jordan曲线定理
Abstract: This paper showed that the number of the shortest cycles in a planar graph of order $n$ is at most $O(n^{2})$ and the bound is the best possible (subject to the power of $n$) since $K_{n-2,n}$ contains exactly $\frac{(n-2)(n-3)}{2}$ many 4-cycles.-
Key words:
- short cycle /
- fundamental cycle /
- Jordan curve theorem
-
[1] {1}BONDY J A, MMURTY U S R. Graph Theory with Applications[M]. London:Macmillan, 1978.{2}THOMASSEN C. Embeddings of graphs with no short noncontractiblecycles[J]. J of Combin Theory Ser B, 1990, 48: 155-177.{3}GR\"{O}TSCH H. Ein Dreifarbensatz f\"{u}r dreikreisfreie Netze aufder Kuge[J]. Wiss Z Martin Luther-Univ Halle Wittenberg, Math-NatReihe, 1959, 8: 109-120.{4}HALFORD T R, CHUGG K M. An algorithm for counting short cycles inBipartite graphs[J]. IEEE Transactions on Information Theory, 2006,52(1): 287-292.{5}MACKAY D J C, NEAL R M. Near Shannon limited performance of lowdensity parity check codes[J]. IEE Electron Lett, 1997, 32(18):1645-1646.{6}REN H, CAO N. Finding short cycles in embedded graphs[J]. Front Mathin China, 2010, 5(2): 319-327. -
点击查看大图
计量
- 文章访问数: 2021
- HTML全文浏览量: 18
- PDF下载量: 1781
- 被引次数: 0
下载: