## The crossing number of the generalized Petersen graph $$P[3k,k]$$.(English)Zbl 1050.05034

Summary: R. K. Guy and F. Harary [Can. Math. Bull. 10, 493–496 (1967; Zbl 0161.20602)] have shown that, for $$k\geq 3$$, the graph $$P[2k,k]$$ is homeomorphic to the Möbius ladder $${M_{2k}}$$, so that its crossing number is one; it is well known that $$P[2k,2]$$ is planar. G. Exoo, F. Harary and J. Kabell [Math. Scand. 48, 184–188 (1981; Zbl 0442.05021)] have shown hat the crossing number of $$P[2k+1,2]$$ is three, for $$k\geq 2.$$ S. Fiorini [Ann. Discrete Math. 30, 225–241 (1986; Zbl 0595.05030)] and R. B. Richter and G. Salazar [Graphs Comb. 18, 381–394 (2002; Zbl 0999.05022)] have shown that $$P[9,3]$$ has crossing number two and that $$P[3k,3]$$ has crossing number $$k$$, provided $$k\geq 4$$. We extend this result by showing that $$P[3k,k]$$ also has crossing number $$k$$ for all $$k\geq 4$$.

### MSC:

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

### Citations:

Zbl 0161.20602; Zbl 0442.05021; Zbl 0595.05030; Zbl 0999.05022
Full Text: