International Journal of Combinatorics
Volume 2011 (2011), Article ID 389369, 14 pages
http://dx.doi.org/10.1155/2011/389369
Research Article

Minimum 2-Tuple Dominating Set of an Interval Graph

Tarasankar Pramanik,1 Sukumar Mondal,2 and Madhumangal Pal1

1Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore 721102, India
2Department of Mathematics, Raja N. L. Khan Women's College, Vidyasagar University, Midnapore 721102, India

Received 8 September 2011; Revised 4 November 2011; Accepted 17 November 2011

Academic Editor: Johannes Hattingh

Copyright © 2011 Tarasankar Pramanik et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

The 𝑘 -tuple domination problem, for a fixed positive integer 𝑘 , is to find a minimum size vertex subset such that every vertex in the graph is dominated by at least 𝑘 vertices in this set. The case when 𝑘 = 2 is called 2-tuple domination problem or double domination problem. In this paper, the 2-tuple domination problem is studied on interval graphs from an algorithmic point of view, which takes 𝑂 ( 𝑛 2 ) time, 𝑛 is the total number of vertices of the interval graph.