Degree equitable restrained double domination in graphs

Sunilkumar M Hosamani, Shailaja Shirkol, Preeti B. Jinagouda, Marcin Krzywkowski


A subset DV(G) is called an equitable dominating set of a graph G if every vertex v ∈ V(G) \ D has a neighbor u D such that |dG(u)-dG(v)| ≤ 1. An equitable dominating set D is a degree equitable restrained double dominating set (DERD-dominating set) of G if every vertex of G is dominated by at least two vertices of D, and 〈V(G) \ D〉 has no isolated vertices. The DERD-domination number of G, denoted by γcl^e(G), is the minimum cardinality of a DERD-dominating set of G. We initiate the study of DERD-domination in graphs and we obtain some sharp bounds. Finally, we show that the decision problem for determining γcl^e(G) is NP-complete.


domination, degree equitable domination, DERD-domination

Full Text:




G. Domke, J. Hatting, S. Hedetniemi, R. Laskar and L. Markus, Restrained domination in graphs, Discrete Math. 203 (2009), 61--69.

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.

F. Harary and T. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201--213.

T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.

T. Haynes, S. Hedetniemi and P. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.

S.M. Hosseini Moghaddam, D.A. Mojdeh, Babak Samadib, Lutz Volkmann, On the signed 2-independence number of graphs, Electron. J. Graph Theory Appl. 5 (1) (2017), 36--42.

N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (1) (2017), 1--6.

R. Kala and T. Vasantha, Restrained double domination number of a graph, AKCE Int. J. Graphs Comb. 5 (2008), 73--82.

V. Kulli, B. Janakiram and R. Iyer, The cototal domination number of a graph, J. Discrete Math. Sci. Cryptogr. 2 (1999), 179--184.

S. J. Seo, P. J. Slater, Open-independent, open-locating-dominating sets, Electron. J. Graph Theory Appl. 5 (2) (2017), 179--193.

V. Swaminathan and K. Dharmalingam, Degree equitable domination on graphs, Kragujevac Journal of Mathematics 35 (2011), 191--197.

E. Vatandoost, F. Ramezani, On the domination and signed domination numbers of zero-divisor graph, Electron. J. Graph Theory Appl. 4 (2) (2016), 148--156.


  • There are currently no refbacks.

ISSN: 2338-2287

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

View EJGTA Stats