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

Abstract

Koh and Tay introduced a new family of graphs, $G$ vertex-multiplications, as an extension of complete $n$-partite graphs. They proved a fundamental classification of $G$ vertex-multiplications into three classes ${\mathcal{C}}_0,{\mathcal{C}}_1$ and ${\mathcal{C}}_2$. It was shown that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ${\mathcal{C}}_2$. Furthermore, for vertex-multiplications of trees with diameter $5$, some necessary and sufficient conditions for ${\mathcal{C}}_0$ were established. In this paper, we give a complete characterisation of vertex-multiplications of trees with diameter $5$ in ${\mathcal{C}}_0$ and ${\mathcal{C}}_1$.

9 pages