## On the crossing number of generalized Petersen graphs.(English)Zbl 0595.05030

Combinatorics ’84, Proc. Int. Conf. Finite Geom. Comb. Struct., Bari/Italy 1984, Ann. Discrete Math. 30, 225-241 (1986).
[For the entire collection see Zbl 0582.00008.]
The generalized Petersen graph P(n,k) has vertex set $$\{a_ 1,a_ 2,...,a_ n,b_ 1,b_ 2,...,b_ n\}$$ and edge set $$\{a_ ib_ i$$, $$a_ ia_{i+1}$$, $$b_ ib_{i+k}$$; $$1\leq i\leq n$$, subscripts mod $$n\}$$. The crossing numbers $$\nu$$ (n,k) of P(n,k) are determined for the following: $$\nu (9,3)=2$$, $$\nu (3h,3)=h$$ (h$$\geq 4)$$, $$\nu (3h+2,3)=h+2$$, $$h+1\leq \nu (3h+1,3)\leq h+3$$, $$\nu (4h,4)=2h$$. Various conjectures are formulated. The employed techniques contain some conclusions of a general nature which could be possibly used in determining lower bounds on crossing numbers of some graphs.
Reviewer: J.Širáň

### MSC:

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

### Keywords:

generalized Petersen graph; crossing numbers

Zbl 0582.00008