DOI: 10.2298/aadm241217027h ISSN: 1452-8630

Crossing number of graphs and ΔY-move

Youngsik Huh, Ryo Nikkuni
Show PDF Cite

In this paper we investigate the behavior of crossing number under a graph transformation, called ΔY-move, on the complete graph \mathrm{K_n} . Concretely it is shown that for any k ∈ N, there exist a natural number n and a sequence of ΔY-moves \mathrm{K_n} → G^{(1)} → ...→ G^{(k)} which is strictly decreasing with respect to the crossing number, that is, cr( \mathrm{K_n} ) > cr( G^{(1)} ) >... > cr( G^{(k)} ) . We also discuss the decrease of crossing number for n = 6, 7.

More from our Archive