Some Combinatorial Problems on Halin Graphs

Abstract

Let $T$ be a tree with no degree 2 vertices and $L(T)=\{l_1,\dots ,l_r\},r\ge 2$ denote the set of leaves in $T$. An Halin graph $G$ is a graph obtained from $T$ such that $V(G)=V(T)$ and $E(G)=E(T)\cup \{\{l_i,l_{i+1}\}|1\le i\le r-1\}\cup \{l_1,l_r\}$. In this paper, we investigate combinatorial problems such as, testing whether a given graph is Halin or not, chromatic bounds, an algorithm to color Halin graphs with the minimum number of colors. Further, we present polynomial-time algorithms for testing and coloring problems.