Degree Sequences of Halin Graphs, and Forcibly Cograph-graphic Sequences

Abstract

A sequence $\pi =(d_1,\dots ,d_n)$ of nonnegative integers is graphic if there exists a graph $G$ with $n$ vertices for which $d_1,\dots ,d_n$ are the degrees of its vertices. $G$ is referred to as a realization of $\pi$. Let $P$ be a graph property. A graphic sequence $\pi$ is potentially $P$-graphic if there exists a realization of $\pi$ with the graph property $P$. Similarly, $\pi$ is forcibly $P$-graphic if all realizations of $\pi$ have the property $P$. We characterize potentially Halin graph-graphic sequences, forcibly Halin graph-graphic sequences, and forcibly cograph-graphic sequences.