Estimating the number of short cycles in simple planar graphs

TANG Bao-xiang; SHI Li-hua; REN Han

Issue 1

Jan. 2013

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2013 > (1): 11-16

TANG Bao-xiang, SHI Li-hua, REN Han. Estimating the number of short cycles in simple planar graphs[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 11-16.

Citation:

TANG Bao-xiang, SHI Li-hua, REN Han. Estimating the number of short cycles in simple planar graphs[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 11-16.

TANG Bao-xiang, SHI Li-hua, REN Han. Estimating the number of short cycles in simple planar graphs[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 11-16.

Citation:

TANG Bao-xiang, SHI Li-hua, REN Han. Estimating the number of short cycles in simple planar graphs[J]. Journal of East China Normal University (Natural Sciences), 2013, (1): 11-16.

PDF( 283 KB)

Estimating the number of short cycles in simple planar graphs

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 Date: 2011-12-01
Rev Recd Date: 2012-03-01
Publish Date: 2013-01-25

Abstract

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.
- short cycle,
- fundamental cycle,
- Jordan curve theorem

FullText(HTML)

References(1)

References

[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 noncontractible

cycles[J]. J of Combin Theory Ser B, 1990, 48: 155-177.
{3}

GR\"{O}TSCH H. Ein Dreifarbensatz f\"{u}r dreikreisfreie Netze auf

der Kuge[J]. Wiss Z Martin Luther-Univ Halle Wittenberg, Math-Nat

Reihe, 1959, 8: 109-120.
{4}

HALFORD T R, CHUGG K M. An algorithm for counting short cycles in

Bipartite 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 low

density 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 Math

in China, 2010, 5(2): 319-327.

Relative Articles

Supplements(0)

Cited By

Proportional views