Maximal Degree Domination in Graphs

Abstract

A set $S$ of vertices in a graph $G$ is called a dominating set if every vertex in $V-S$ is adjacent to at least one vertex in $S$. A maximal degree dominating function $(MDDF)$ is a type of function $f:V(G)\arrowvert\left\lbrace 0,1,2,3, ...,(\bigtriangleup(G)+1)\right\rbrace $ having the property that every $v$ in $S$ is assigned the value $deg(v)+1$, and all remaining vertices with zero. The weight of a maximal degree dominating function $f$ is defined by $w(f)=\ds \sum_{v\in S}deg(v)+1$. The maximal degree domination number $\gamma_{mdeg}(G)$ is the minimum weight among all possible $MDDFs$. In this paper, we determine its exact value.