Minimal and Upper Cost Effective Domination in Graphs

Authors

DOI:

https://doi.org/10.29020/nybg.ejpam.v14i2.3955

Keywords:

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

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.

Author Biography

  • Hearty Nuenay Maglanque, University of Science and Technology of Southern Philippines

    Department of Applied Mathematics, 

    Assistant Professor III

Downloads

Published

2021-05-18

Issue

Section

Nonlinear Analysis

How to Cite

Minimal and Upper Cost Effective Domination in Graphs. (2021). European Journal of Pure and Applied Mathematics, 14(2), 537-550. https://doi.org/10.29020/nybg.ejpam.v14i2.3955