Abstract

A graph could be understood as a sensor network, in which the vertices represent the sensors and two vertices are adjacent if and only if the corresponding devices can communicate with each other. For a network G, a 2-dominating function on G is a function f : V(G) → [0, 1] such that each vertex assigned with 0 has at least two neighbors assigned with 1. The weight of f is Σ_u∈V(G) f (u), and the minimum weight over all 2-dominating functions is the 2-domination number of G. The 2-dominating set problem consists of finding the 2-domination number of a graph and it was proposed to model the fault tolerance of a sensor network. In this paper, we determined substantial 2-domination numbers of 2-dimensional meshes, cylinders, tori and hypercubes.

This work is licensed under a Creative Commons Attribution 4.0 License.