Application of some techniques in Sperner Theory: Optimal orientations of vertex-multiplications of trees with diameter 4
| Autor: | Wong, W. H. W., Tay, E. G. |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Theory Appl. Graphs, 10, (2023), Article 6 |
| Druh dokumentu: | Working Paper |
| Popis: | Koh and Tay proved a fundamental classification of $G$ vertex-multiplications into three classes $\mathscr{C}_0, \mathscr{C}_1$ and $\mathscr{C}_2$. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class $\mathscr{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 $\mathscr{C}_0$ (or $\mathscr{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$. Comment: 78 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|