Embedding of circulant graphs and generalized Petersen graphs on projective plane

摘要

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 + l;{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.