The [a,b]-domination and [a,b]-total Domination of Graphs

Xiujun Zhang, Zehui Shao and Hong Yang

Journal of Mathematics Research, 2017, vol. 9, issue 3, 38-45

Abstract: A subset $S$ of the vertices of $G = (V, E)$ is an $[a, b]$-set if for every vertex $v$ not in $S$ we have the number of neighbors of $v$ in $S$ is between $a$ and $b$ for non-negative integers $a$ and $b$, that is, every vertex $v$ not in $S$ is adjacent to at least $a$ but not more than $b$ vertices in $S$. The minimum cardinality of an $[a, b]$-set of $G$ is called the $[a, b]$-domination number of $G$. The $[a, b]$-domination problem is to determine the $[a, b]$-domination number of a graph. In this paper, we show that the [2,b]-domination problem is NP-complete for $b$ at least $3$, and the [1,2]-total domination problem is NP-complete. We also determine the [1,2]-total domination and [1,2] domination numbers of toroidal grids with three rows and four rows.

Keywords: [a; b]-domination; [a; b]-total domination; NP-complete; toroidal grids (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.ccsenet.org/journal/index.php/jmr/article/view/66426/37061 (application/pdf)
http://www.ccsenet.org/journal/index.php/jmr/article/view/66426 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ibn:jmrjnl:v:9:y:2017:i:3:p:38-45

Access Statistics for this article

More articles in Journal of Mathematics Research from Canadian Center of Science and Education Contact information at EDIRC.
Bibliographic data for series maintained by Canadian Center of Science and Education ().