Embedding of circulant graphs and generalized Petersen graphs on projective plane

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.

Keywords

Embedding / joint tree / circulant graph / generalized Petersen graph / projective plane

References

[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

[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

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

[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

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

[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

[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

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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg