×

The Euler genera of two classes of generalized Petersen graphs. (Chinese. English summary) Zbl 1199.05074

Summary: The generalized Petersen graph \(P(n,m)\) is such a graph that its vertex set is \(\{u_i,v_i \,|\, i=0,1,\dots ,n-1\}\) and its edge set is \(\{u_iu_{i+1},v_iv_{i+m},u_iv_i \,|\, i=0,1,\dots ,n-1\}\), where \(m,n\) are positive integers satisfying \(m<\lfloor \frac n2\rfloor\) and indices are read modulo \(n\). It is proved that the Euler genus of \(P(2m+1,m)\) (\(m\geq 2\)) is 1 and that the Euler genus of \(P(2m+2,m)\) (\(m\geq 5\)) is 2.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite