Constructing regular graphs with smallest defining number

MaRDI QIDQ3011701zbMATH OpenFDO

Authors Behnaz Omoomi, Nasrin Soltankhah

Publication date 29 June 2011

Full work available at URL https://arxiv.org/abs/0806.1395

zbMATH Keywords

colouringdefining setregular graphuniquely extendible colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $ngeq3k$, if $rgeq2(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 $rgeq2(k-1)$, $d(n,r,Cchi=k)=k-1$.

Recommendations

• scientific article; zbMATH DE number 5064065
• On the defining number of (2n-2)-vertex colorings of K_n K_n
• On defining numbers of vertex colouring of regular graphs
• The defining numbers for vertex colorings of certain graphs
• On defining numbers of k-chromatic k-regular graphs.

Cited in

(4)

• On defining numbers of vertex colouring of regular graphs
• scientific article; zbMATH DE number 94782 (Why is no real title available?)
• On defining numbers of k-chromatic k-regular graphs.
• scientific article; zbMATH DE number 5064065 (Why is no real title available?)

This page was built for publication: Constructing regular graphs with smallest defining number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3011701)