Minimal and Upper Cost Effective Domination in Graphs

Hearty Nuenay Maglanque, Ferdinand P. Jamil

Abstract

Given a connected graph $G$, we say that $S\subseteq 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.

Keywords

cost effective dominating set, minimal cost effective dominating set, minimal cost effective domination number, upper cost effective domination number

Full Text:

PDF