On the crossing numbers of loop networks and generalized Petersen graphs (Q2575797): Difference between revisions

The crossing number of a graph is the minimum number of edge-crossings in a drawing in the plane. Hlinený showed that the crossing number is hard to compute, even for cubic graphs [see \textit{P. Hlinený}, Lect. Notes Comput. Sci. 3153, 772--782 (2004; Zbl 1097.68047)]. Little is known about crossing numbers of special graphs, see \textit{S. Fiorini} and \textit{J. Baptist Gauci} [Math.\ Bohem.\ 128, 337--347 (2003; Zbl 1050.05034)] or \textit{M. L. Saražin} [Math. Slovaca 47, 189--192 (1997; Zbl 1053.05507)] for related results and further references. \(G(n; \pm 1, \pm k)\) is the graph obtained from an \(n\)-cycle by adding all chords between vertices in distance \(k\). For \(k \geq 5\) and \(n \geq k^2\) the bounds \((1 - 4/k)n + (4k^2 + 1 - k^3) \leq \text{cr}(G(n; \pm 1, \pm k)) \leq (1 - 2/k)n + (k^2/2 + k/2 + 1)\) are shown. For the generalised Petersen graph \(P(n,k)\) with \(n \geq k \geq 5\), the bounds are \((2/5)(1 - 4/k)(n-k^4) + (4k^2 + 1 - k^3) \leq \text{cr}(P(n,k)) \leq (2 - 2/k)n + (k^2/2 + k/2 + 1)\).