Constructing regular graphs with smallest defining number

Details Constructing regular graphs with smallest defining number Constructing regular graphs with smallest defining number

2008-06-09

arxiv.org/abs/0806.1395v1

Mathematics

Combinatorics

13 pages. to appear in ARS Combinatoria

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Constructing regular graphs with smallest defining number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructing regular graphs with smallest defining number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing regular graphs with smallest defining number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400529