A Note on The Complexity of Graph Parameters and The Uniqueness of their Realizations

Abstract

Let $\nu$ be some graph parameter and let $\mathcal{G}$ be a class of graphs for which $\nu$ can be computed in polynomial time. In this situation, it is often possible to devise a strategy to decide in polynomial time whether $\nu$ has a unique realization for some graph in $\mathcal{G}$. We first give an informal description of the conditions that allow one to devise such a strategy, and then we demonstrate our approach for three well-known graph parameters: the domination number, the independence number, and the chromatic number.