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\le 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\le 5$. They raised the following question: Is it true that for every $k$, there exists $n_0(k)$ such that for all $n\ge 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$.