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.