“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 2316  


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 kchromatic uniquely
vertex colourable graph from a kchromatic graph G on G∪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}−index and τ_{r}−index(r=0,1) for graphs. In this approach we show the existence of
certain classes of ucores, for which, the existence of an
extremal graph provides a counter example for Xu's conjecture.
Download TeX format 

back to top 