Application of some techniques in Sperner Theory: Optimal orientations of vertex-multiplications of trees with diameter 4

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$. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ${\mathcal{C}}_2$. Of interest, $G$ vertex-multiplications are extensions of complete $n$-partite graphs and Gutin characterised complete bipartite graphs with an ingenious use of Sperner's Theorem. In this paper, we investigate vertex-multiplications of trees with diameter $4$ in ${\mathcal{C}}_0$ (or ${\mathcal{C}}_1$) and exhibit its intricate connections with problems in Sperner Theory, thereby extending Gutin's approach. Let $s$ denote the vertex-multiplication of the central vertex. We almost completely characterise the case of even $s$ and give a complete characterisation for the case of odd $s\ge 3$.

78 pages