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

Fiorini, Stanley; Baptist Gauci, John

Math. Bohem. 128, No. 4, 337-347 (2003).

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

Keywords:

graph; drawing; crossing number; generalized Petersen graph; Cartesian product

Citations:

Zbl 0161.20602; Zbl 0442.05021; Zbl 0595.05030; Zbl 0999.05022