On Some Parameters Related to Uniquely Vertex-Colourable Graphs and Defining Sets

Abstract

We consider two possible methods of embedding a (simple undirected) graph into a uniquely vertex colourable graph. The first method considered is to build a $K$-chromatic uniquely vertex colourable graph from a $k$-chromatic graph $G$ on $G\cup K_k$, by adding a set of new edges between the two components. This gives rise to a new parameter called fixing number (Daneshgar (1997)). Our main result in this direction is to prove that a graph is uniquely vertex colourable if and only if its fixing number is equal to zero (which is a counterpart to the same kind of result for defining numbers proved by Hajiabolhassan et al. (1996)).

In our second approach, we try a more subtle method of embedding which gives rise to the parameters $t_r$-fixer and ${\tau }_r$-index ($r=0,1$) for graphs. In this approach we show the existence of certain classes of $u$-cores, for which, the existence of an extremal graph provides a counter example for Xu’s conjecture.