• 1
  • 1
  • 6
  • 5
  • 6
  • 3
  • 4

“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2316
School of Mathematics
  Title:   On some parameters related to uniquely vertex-colorable graphs and defining sets
  Author(s): 
1.  A. Daneshgar
2.  R. Naserasr
  Status:   Published
  Journal: Ars Combin.
  Vol.:  69
  Year:  2003
  Pages:   301-318
  Supported by:  IPM
  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 GKk 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 trindex and τrindex(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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right