Constructing regular graphs with smallest defining number
| dc.creator | Omoomi, Behnaz | |
| dc.creator | Soltankhah, Nasrin | |
| dc.date | 2008-06-09 | |
| dc.date.accessioned | 2026-07-07T09:43:21Z | |
| dc.date.available | 2026-07-07T09:43:21Z | |
| dc.description | In a given graph $G$, a set $S$ of vertices with an assignment of colors is a {\sf defining set of the vertex coloring of $G$}, if there exists a unique extension of the colors of $S$ to a $\Cchi(G)$-coloring of the vertices of $G$. A defining set with minimum cardinality is called a {\sf smallest defining set} (of vertex coloring) and its cardinality, the {\sf defining number}, is denoted by $d(G, \Cchi)$. Let $ d(n, r, \Cchi = k)$ be the smallest defining number of all $r$-regular $k$-chromatic graphs with $n$ vertices. Mahmoodian et. al \cite{rkgraph} proved that, for a given $k$ and for all $n \geq 3k$, if $r \geq 2(k-1)$ then $d(n, r, \Cchi = 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, \Cchi=k)=k-1$. | |
| dc.description | 13 pages. to appear in ARS Combinatoria | |
| dc.identifier | https://arxiv.org/abs/0806.1395 | |
| dc.identifier | http://arxiv.org/abs/0806.1395 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162522 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C xx | |
| dc.title | Constructing regular graphs with smallest defining number | |
| dc.type | text |