UVictoria Discrete Math Seminar: Meng-ru Lin

Let $T$ be a tree in which no vertex has degree $2$. A Halin graph is a planar graph obtained by connecting all leaves of $T$ into a cycle in their planar order. The idea of universal originates from a question of John W. Moon (1965). Consider all tournaments on n vertices (there are $2^{n(n-1)/2}$ such tournaments), and let $G$ be the disjoint union of all the tournaments. Is there an oriented graph $H$ such that $G$ admits a homomorphism to $H$? Moreover, what is the minimum possible order of such a graph $H$? In this talk, we show that if $G$ is the disjoint union of all Halin graphs with all possible orientations, then $G$ admits a homomorphism to an oriented graph of order $14$. That is, the smallest universal of Halin graphs has order at most $14$.