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


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 rregular rchromatic graphs with n vertices is determined,
for r=2,3,4, and 5.
Download TeX format 

back to top 