| Title |
Minimal and Upper Cost Effective Domination Number in Graphs |
|
Authors |
H. Nuenay-Manlanque and F. Jamil |
|
Publication date |
2021 |
|
Journal |
European Journal of Pure and Applied Mathematics |
| Volume |
14 |
| Issue |
2 |
| Pages |
537-550 |
| Publisher |
New York Business Global |
| Abstract |
Given a connected graph G, we say that $Ssubseteq V(G)$ is a cost effective dominating set in $G$ if, each vertex in $S$ is adjacent to at least as many vertices outside $S$ as inside $S$ and that
every vertex outside $S$ is adjacent to at least one vertex in $S$. The minimum cardinality of a cost effective dominating set is the cost effective domination number of $G$. The maximum cardinality of
a cost effective dominating set is the upper cost effective domination number of $G$, and is denoted by $gamma_{ce}^+(G)$. A cost effective dominating set is said to be minimal if it does not contain a proper
subset which is itself a cost effective dominating in $G$. The maximum cardinality of a minimal cost effective dominating set in a graph $G$ is the minimal cost effective domination number of $G$, and is denoted by
$gamma_{mce}(G)$. In this paper we provide bounds on upper cost effective domination number and minimal cost effective domination number of a connected graph $G$ and characterized those graphs whose upper and minimal cost effective domination numbers are either $1$, $2$ or $n - 1$. We also establish a Nordhaus-Gaddum type result for the introduced parameters and solve some realization problems. |
| Index terms / Keywords |
cost effective dominating set, minimal cost effective dominating set, minimal cost effective domination number, upper cost effective domination number |
| DOI |
DOI: https://doi.org/10.29020/nybg.ejpam.v14i2.3955 |
| URL |
|
Mindanao State
University - Iligan Institute of Technology