k-Efficient partitions of graphs

Document Type : Original paper

Authors

1 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

2 Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-0002 USA

3 Professor Emeritus, School of Computing, Clemson University, Clemson, SC 29634 USA

Abstract

A set S={u1,u2,…,ut} of vertices of G is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. Letting Ui denote the set of vertices dominated by ui, we note that {U1,U2,…Ut} is a partition of the vertex set of G and that each Ui contains the vertex ui and all the vertices at distance~1 from it in G. In this paper, we generalize the concept of efficient domination by considering k-efficient domination partitions of the vertex set of G, where each element of the partition is a set consisting of a vertex ui and all the vertices at distance~di from it, where di∈{0,1,…,k}. For any integer k≥0, the k-efficient domination number of G equals the minimum order of a k-efficient partition of G. We determine bounds on the k-efficient domination number for general graphs, and for k∈{1,2}, we give exact values for some graph families. Complexity results are also obtained. 

Keywords

Main Subjects

References

[1] D.W. Bange, A.E. Barkauskas, and P.J. Slater, Efficient dominating sets in graphs, Applications of Discrete Math. , R. D. Ringeisen and F. S. Roberts, eds., SIAM, Philadelphia (1988), 189–199.
[2] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006), no. 1, 59–75.
[3] D.J. Erwin, Dominating broadcasts in graphs, Bull. Inst. Comb. Appl. 42 (2004), 89–105.
[4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[5] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983), 33–44.
[6] A. Meir and J. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), no. 1, 225–233.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 109-122

Files

Share

How to cite

Statistics