On Defining Numbers of \(k\)—Chromatic \(k\)—Regular Graphs

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)\). We study the defining number of regular graphs. Let \(d(n,r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices, and \(f(n,k) = \frac{k-2}{2(k-1)} +\frac{2+(k-2)(k-3)}{2(k-1)}\). Mahmoodian and Mendelsohn (1999) determined the value of \(d(n,k, \chi = k)\) for all \(k \leq 5\), except for the case of \((n,k) = (10,5)\). They showed that \(d(n,k, \chi = k) = \lceil f(n,k) \rceil\), for \(k \leq 5\). They raised the following question: Is it true that for every \(k\), there exists \(n_0(k)\) such that for all \(n \geq n_0(k)\), we have \(d(n,k, \chi = k) = \lceil f(n,k) \rceil\)?

Here we determine the value of \(d(n,k, \chi = k)\) for each \(k\) in some congruence classes of \(n\). We show that the answer for the question above, in general, is negative. Also, for \(k = 6\) and \(k = 7\) the value of \(d(n,k, \chi = k)\) is determined except for one single case, and it is shown that \(d(10,5, \chi = 5) = 6\).