“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 166
School of Mathematics
  Title:   On defining numbers of vertex colouring of regular graphs
  Author(s): 
1.  E. S. Mahmoodian
2.  E. Mendelsohn
  Status:   Published
  Journal: Discrete Math.
  Vol.:  197/198
  Year:  1999
  Pages:   543-554
  Supported by:  IPM
  Abstract:
In a given graph G, a set S of vertices with an assignment of colours to them is a defining set of the vertex colouring of G, if there exists a unique extension of the colours of S to a χ(G)- olouring of the vertices of G. defining set with minimum cardinality is called a minimum defining set (of vertex colouring) and its cardinality, the defining number, is denoted by d(G,χ). Mahmoodian et al have studied this concept. Here we study the defining numbers of regular graphs. Among other results the exact value of d(n,r,χ = r), the minimum defining number of all r-regular r-chromatic graphs with n vertices is determined, for r=2,3,4, and 5.

Download TeX format
back to top
scroll left or right