Abstract:

A subset of vertices in a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex within the subset. Two non-total dominating sets form a total coalition in a graph if their union is a total dominating set. A partition $\pi$ of graph vertices into non-total dominating sets is a total coalition partition if every set of $\pi$ forms a total coalition set with at least one other set of $\pi$.  Vertices of the total coalition graph $TCG(G,\pi)$ correspond with the sets of $\pi$, and two vertices are adjacent in $TCG(G,\pi)$  if and only if the corresponding sets constitute a total coalition. We  show that $C_{4k}$ is a  universal total coalition cycle for $k\ge2$, that is, a cycle whose total coalition partitions generate all possible total coalition graphs of cycles.  We also demonstrate that $P_n$ is a universal total coalition path for $n \ge 5$.