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 |