Article in press
Authors:
Title:
Restrained differential of a graph
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-06-06 , Revised: 2023-11-16 , Accepted: 2023-11-21 , Available online: 2023-12-08 , https://doi.org/10.7151/dmgt.2532
Abstract:
Given a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood}
of $v$ is defined to be $N(v)=\{u\in V(G): uv\in E(G)\}$. The {external
neighbourhood} of a set $S\subseteq V(G)$ is defined as
$S_e=\left(\bigcup_{v\in S}N(v)\right)\setminus S$, while the restrained
external neighbourhood of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e
\neq \emptyset\}$. The restrained differential of a graph $G$ is defined as
$\partial_r(G)=\max \{|S_r|-|S|: S\subseteq V(G)\}.$ In this paper, we
introduce the study of the restrained differential of a graph. We show that
this novel parameter is perfectly integrated into the theory of domination in
graphs. We prove a Gallai-type theorem which shows that the theory of
restrained differentials can be applied to develop the theory of restrained
Roman domination, and we also show that the problem of finding the restrained
differential of a graph is NP-hard. The relationships between the restrained
differential of a graph and other types of differentials are also studied.
Finally, we obtain several bounds on the restrained differential of a graph
and we discuss the tightness of these bounds.
Keywords:
differentials in graphs, restrained differential, restrained Roman domination
References:
- H. Abdollahzadeh Ahangar and S.R. Mirmehdipour, Bounds on the restrained Roman domination number of a graph, Commun. Comb. Optim. 1 (2016) 75–82.
https://doi.org/10.22049/cco.2016.13556 - S. Bermudo, On the differential and Roman domination number of a graph with minimum degree two, Discrete Appl. Math. 232 (2017) 64–72.
https://doi.org/10.1016/j.dam.2017.08.005 - S. Bermudo, H. Fernau and J.M. Sigarreta, The differential and the Roman domination number of a graph, Appl. Anal. Discrete Math. 8 (2014) 155–171.
https://doi.org/10.2298/AADM140210003B - S. Bermudo, J.M. Sigarreta and J.M. Rodríguez, On the differential in graphs, Util. Math. 97 (2015) 257–270.
- A. Cabrera Martínez and J.A. Rodríguez-Velázquez, On the perfect differential of a graph, Quaest. Math. 45 (2022) 327–345.
https://doi.org/10.2989/16073606.2020.1858992 - A. Cabrera Martínez and J.A. Rodríguez-Velázquez, From the strong differential to Italian domination in graphs, Mediterr. J. Math. 18 (2021) 228.
https://doi.org/10.1007s00009-021-01866-7 - A. Cabrera Martínez, M.L. Puertas and J.A. Rodríguez-Velázquez, On the $2$-packing differential of a graph, Results Math. 76 (2021) 157.
https://doi.org/10.1007/s00025-021-01473-8 - E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22.
https://doi.org/10.1016/j.disc.2003.06.004 - G.S. Domke, J.H. Hattingh, S.T. Hedetniemi R.C. Laskar and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61–69.
https://doi.org/10.1016/S0012-365X(99)00016-3 - W. Goddard and M.A. Henning, Generalised domination and independence in graphs, Congr. Numer. 123 (1997) 161–171.
- N. Jafari Rad and M. Krzywkowski, On the restrained Roman domination in graphs (2004), manuscript.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
https://doi.org/10.1201/9781482246582 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
- J.L. Lewis, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, Differentials in graphs, Util. Math. 69 (2006) 43–54.
- P.R.L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4(1) (2015) 1–17.
https://doi.org/10.22108/toc.2015.4395 - P.R.L. Pushpam and D. Yokesh, Differentials in certain classes of graphs, Tamkang J. Math. 41(2) (2010) 129–138.
https://doi.org/10.5556/j.tkjm.41.2010.664 - F. Siahpour, H. Abdollahzadeh Ahangar and S.M. Sheikholeslami, Some progress on the restrained Roman domination, Bull. Malays. Math. Sci. Soc. 44 (2021) 733–751.
https://doi.org/10.1007/s40840-020-00965-0
Close