Physical Sciences and Mathematics Commons^™

Optimal Orientations Of Vertex-Multiplications Of Trees With Diameter 4, Willie Han Wah Wong, Eng Guan Tay

Theory and Applications of Graphs

Koh and Tay proved a fundamental classification of G vertex-multiplications into three classes ζ₀, ζ₁ and ζ₂. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ζ₂. Of interest, G vertex-multiplications are extensions of complete n-partite graphs and Gutin characterised complete bipartite graphs with orientation number 3 (or 4 resp.) via an ingenious use of Sperner's theorem. In this paper, we investigate vertex-multiplications of trees with diameter 4 in ζ₀ (or ζ₁) and exhibit its intricate connections with …