Bounds for the 2-domination number of toroidal grid graphs

Abstract

A k-dominating set for a graph G(V, E) is a set of vertices D⊆ V such that every vertex v∈V\ D is adjacent to at least k vertices in D. The k-domination number of G, denoted by γ _k (G), is the cardinality of a smallest k-dominating set of G. Here we establish lower and upper bounds of γ _k (C _m ×C _n ) for k=2. In some cases, these bounds agree so that the exact 2-domination number is obtained.

Keywords:

• k-domination
• k-dominating set
• graph products
• cycles
• toroidal
• grid graph

AMS Subject Classification :

• 05C99