Constructing Regular Graphs with Smallest Defining Number

Abstract

In a given graph \(G\), a set \(S\) of vertices with an assignment of colors is a defining set of the vertex coloring of \(G\), if there exists a unique extension of the colors of \(S\) to a \(\chi(G)\)-coloring of the vertices of \(G\). A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by \(d(G, \chi)\). Let \(d(n, r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices. Mahmoodian \(et.\; al [7]\) proved that, for a given \(k\) and for all \(n \geq 3k\), if \(r \geq 2(k-1)\) then \(d(n, r, \chi = k) = k-1\). In this paper we show that for a given \(k\) and for all \(n < 3k\) and \(r \geq 2(k – 1)\), \(d(n, r, \chi = k) = k-1\).