Cost Effective Domination in the Join, Corona and Composition of Graphs

Ferdinand P. Jamil, Hearty Nuenay Maglanque

Abstract

Let $G$ be a connected graph. A cost effective dominating set in a graph $G$ is any set $S$ of vertices in $G$ satisfying the condition that each vertex in $S$ is adjacent to at least as many vertices outside $S$ as inside $S$ and 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$. 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$.

In this paper, we characterized the cost effective dominating sets in the join, corona and composition of graphs. As direct consequences, we the bounds or the exact cost effective domination numbers, minimal cost effective domination numbers and upper cost effective domination numbers of these graphs were obtained.

Keywords

cost effective domination, cost effective dominating sets, join, corona and composition

Full Text:

PDF