Journal of East China Normal University(Natural Sc ›› 2013, Vol. 2013 ›› Issue (1): 11-16.

• Article • Previous Articles     Next Articles

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

1945

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

CLC Number: