华东师范大学学报(自然科学版) ›› 2013, Vol. 2013 ›› Issue (1): 11-16.

• 应用数学与基础数学 • 上一篇    下一篇

简单平面图中短圈数目的估计

唐保祥1, 施莉骅2, 任 韩2   

  1. 1. 天水师范学院~~数学与统计学院, 甘肃 741001;
    2. 华东师范大学~~数学系, 上海 200241
  • 收稿日期:2011-12-01 修回日期:2012-03-01 出版日期:2013-01-25 发布日期:2013-01-18

Estimating the number of short cycles in simple planar graphs

TANG Bao-xiang 1, SHI Li-hua 2, REN Han 2   

  1. 1. School of Mathematics and Statistics Institute, Tianshui Normal University, Gansu 741001, China;
    2. Department of Mathematics, East China Normal University, Shanghai 200241, China
  • Received:2011-12-01 Revised:2012-03-01 Online:2013-01-25 Published:2013-01-18

PDF

1950

摘要： 证明一个\,$n$\,阶简单\,$2$-连通平面图\,$G$\,中至多有\,$O(n^{2})$\,个最短圈\,(即存在绝对常数\,$c>0$\,使得\,$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

中图分类号: