On Restrained Domination Number of Graphs

S K Vaidya, P D Ajani


For a graph $G=(V,E)$, a set $S \subseteq V$ is a restrained dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V-S$. The smallest cardinality of a restrained dominating set of $G$ is called restrained domination number of $G$, denoted by $\gamma_r (G)$. We investigate restrained domination number of some cycle related graphs which are obtained by means of various graph operations on cycle.

Full Text:



M. E. Abdel-Aal, New Classes of Odd Graceful Graphs, International journal on applications

of graph theory in wireless ad hoc networks and sensor networks, 5(2) (2013).

M. Alishahi and S. H. Shalmaee, Domination Number of Square of Cartesian Products of Cycles,

Open Journal of Discrete Mathematics, 5(2015), 88-94.

C. Berge, Theory of Graphs and its Applications, Methuen, London, 1962.

E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total Domination in Graphs, Networks,

(1980), 211-219.

P. Dankelmann, J. H. Hattingh, M. A. Henning and H. C. Swart, Trees with Equal Domination

and Restrained Domination Numbers, J. Global Optim., 34(2006), 597-607.

G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar and L. R. Markus, Restrained

Domination in Graphs, Discrete Mathematics, 203(1999), 61-69.

G. S. Domke, J. H. Hattingh, M. A. Henning and L. R. Markus, Restrained Domination in

Graphs with Minimum Degree Two, J. Combin. Math.Combin. Comput., 35(2000), 239-254.

G. S. Domke, J. H. Hattingh, M. A. Henning and L. R. Markus, Restrained Domination in

Trees, Discrete Math., 211(2000), 1-9.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs,

Marcel Dekker, New York, 1998.

O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence,

RI), 1662.

E. Sampathkumar, The Global Domination Number of a Graph, Journal of Mathematical and

Physical Sciences, 23(5) (1989), 377-385.

V. Swaminathan and K. M. Dharmalingam, Degree Equitable Domination on Graphs, Kragujevac

Journal of Mathematics, 35(1) (2011), 191-197.

J. A. Telle and A. Proskurowski, Algorithms for Vertex Partitioning Problems on Partial k-trees,

SIAM J. Discrete Mathematics, 10(1997), 529-550.


  • There are currently no refbacks.

Web Counters

IJMSC has been indexed in several world class data bases like Google Scholar, DRJI (Directory of Research Journals Indexing) ,Cite Factor, Research Bible.

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