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

  •  Xiujun Zhang    
  •  Zehui Shao    
  •  Hong Yang    


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.

This work is licensed under a Creative Commons Attribution 4.0 License.
  • ISSN(Print): 1916-9795
  • ISSN(Online): 1916-9809
  • Started: 2009
  • Frequency: bimonthly

Journal Metrics

  • h-index (February 2019): 18
  • i10-index (February 2019): 48
  • h5-index (February 2019): 7
  • h5-median (February 2019): 10

( The data was calculated based on Google Scholar Citations. Click Here to Learn More. )