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

Fiorini, S.

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

Citations:

Zbl 0582.00008