Optimal orientations of vertex-multiplications of cartesian products of graphs

Abstract

Koh and Tay proved a fundamental classification of $G$ vertex-multiplications into three classes ${\mathcal{C}}_0,{\mathcal{C}}_1$ and ${\mathcal{C}}_2$. In this paper, we prove that vertex-multiplications of cartesian products of graphs $G\times H$ lie in ${\mathcal{C}}_0$ (${\mathcal{C}}_0\cup {\mathcal{C}}_1$ resp.) if $G^{(2)}\in {\mathcal{C}}_0$ (${\mathcal{C}}_1$ resp.), $d(G)\ge 2$ and $d(G\times H)\ge 4$. We also focus on cartesian products involving trees, paths and cycles and show that most of them lie in ${\mathcal{C}}_0$.

28 pages

References in corpus (1)

• A complete characterisation of vertex-multiplications of trees with diameter 5