Journal
Title | Minimal and Upper Cost Effective Domination Number in Graphs Posted by Ferdinand Jamil |
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 | http://www.ejpam.com |