“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 k-chromatic uniquely
vertex colourable graph from a k-chromatic graph G on G∪Kk 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 tr−index and τ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.
Download TeX format |
|||||
| back to top | |||||
