Frontiers of Mathematics in China >

2015 , Vol. 10 >Issue 1: 209 - 220

DOI: https://doi.org/10.1007/s11464-014-0428-9

RESEARCH ARTICLE

Embedding of circulant graphs and generalized Petersen graphs on projective plane

  • Yan YANG , 1 ,
  • Yanpei LIU 1
Expand
  • 1. Department of Mathematics, Tianjin University, Tianjin 300072, China
  • 2. Department of Mathematics, Beijing Jiaotong University, Beijing 100044, China

Received date: 03 Jan 2013

Accepted date: 05 Aug 2014

Published date: 30 Dec 2014

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

Abstract

Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.

Key words： Embedding; joint tree; circulant graph; generalized Petersen graph; projective plane

Cite this article

Yan YANG , Yanpei LIU . Embedding of circulant graphs and generalized Petersen graphs on projective plane[J]. Frontiers of Mathematics in China, 2015 , 10(1) : 209 -220 . DOI: 10.1007/s11464-014-0428-9

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
Chen Y C. Lower bounds for the average genus of a CF-graph. Electron J Combin, 2010, 17: #R150

2
Chen Y C, Ou L, Zou Q. Total embedding distributions of Ringel ladders. Discrete Math, 2011, 311(21): 2463-2474

DOI

3
Gross J L. Genus distribution of graphs under surgery: adding edges and splitting vertices. New York J Math, 2010, 16: 161-178

4
Gross J L. Genus distributions of cubic outerplanar graphs. J Graph Algorithms Appl, 2011, 15(2): 295-316

DOI

5
Gross J L, Furst M L. Hierarchy for imbedding distribution invariants of a graph. J Graph Theory, 1987, 11: 205-220

DOI

6
Liu Y P. Advances in Combinatorial Maps. Beijing: Northern JiaoTong University Press, 2003 (in Chinese)

7
Liu Y P. Theory of Polyhedra. Beijing: Science Press, 2008

8
Mohar B, Thomassen C. Graphs on Surfaces. Baltimore: The John Hopkins University Press, 2001

9
Poshni M I, Khan I F, Gross J L. Genus distributions of 4-regular outerplanar graphs. Electron J Combin, 2011, 18: #P212

10
Ren H, Deng M. Embeddings of circulant graphs. Acta Math Sci Ser A Chin Ed, 2007, 27: 1148-1154 (in Chinese)

11
Shao Z L, Liu Y P. The genus of a type of graph. Sci China Math, 2010, 53(2): 457-464

DOI

12
Tutte W T. Combinatorial oriented maps. Canad J Math, 1979, 31(5): 986-1004

DOI

13
Wan L X, Liu Y P. Orientable embedding genus distribution for certain types of graphs. J Combin Theory Ser B, 2008, 98(1): 19-32

DOI

14
Wei E L, Liu Y P, Li Z X. The minimal genus of circular graph C(n,m). OR Trans, 2010, 14(3): 11-18

15
Yang Y, Liu Y P. Flexibility of embeddings of bouquets of circles on the projective plane and Klein bottle. Electron J Combin, 2007, 14: #R80

16
Yang Y, Liu Y P. Number of embeddings of circular and Mobius ladders on surfaces. Sci China Math, 2010, 53(5): 1393-1405

DOI

17
Yang Y, Liu Y P. Flexibility of circular graphs C(2n, 2) on the projective plane. Ars Combin, 2011, 101: 75-83

Options
Outlines

/

〈 〉