A New Approach on Roman Graphs

Year 2021, Volume: 13 Issue: 1, 6 - 13, 30.06.2021

Doost Ali Mojdeh , İman Masoumi , Ali Parsian

Abstract

Let $G=(V,E)$ be a simple graph with vertex set $V=V(G)$ and edge set $E=E(G)$. A Roman dominating function (RDF) on a graph $G$ is a function $f:V\rightarrow\{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ such that $f(v)=2$. The weight of $f$ is $\omega(f)=\Sigma_{v\in V}f(v)$. The minimum weight of an RDF on $G$, $\gamma_{R}(G)$, is called the Roman domination number of $G$. $\gamma_{R}(G)\leq 2\gamma(G)$ where $\gamma(G)$ denotes the domination number of $G$. A graph $G$ is called a Roman graph whenever $\gamma_{R}(G)= 2\gamma(G)$. On the other hand, the differential of $X$ is defined as $\partial(X)=|B(X)|-|X|$ and the differential of a graph $G$, written $\partial(G)$, is equal to $max\{\partial(X): X\subseteq V\}$. By using differential we provide a sufficient and necessary condition for the graphs to be Roman. We also modify the proof of a result on Roman trees. Finally we characterize the large family of trees $T$ such that $\partial(T)=n-\gamma(T)-2$.

Keywords

Roman Domination, Roman graphs, dominant differential graphs

References

• [1] Abdollahzadeh Ahangar, H. , Amjadi, J. , Chellali, M. , Nazari-Moghaddam, S. , Sheikholeslami, S. M. , Trees with Double Roman Domination Number Twice the Domination Number Plus Two, Iranian Journal of Science and Technology, Transactions A: Science, (2018), 1–8.
• [2] Arquilla, J. , Fredricksen, H., Graphing an optimal grand strategy, Military Operations Research 3(1995), 3–17.
• [3] Bermudo, S. , Fernau, H. , Sigarreta, J.M., The dierential and the Roman domination number of a graph, Applicable Analysis and DiscreteMathematics, 8(2014) 155–171.
• [4] Beeler, R.A , Haynes, T. W. , Hedetniemi, S.T., Double Roman domination, Discrete Appl Math 211(2016) 23–29.
• [5] Bermudo, S. , Hernandez-Gomez, J.C. , Rodriguez, J.M. , Sigarreta, J.M., Relations between the dierential and parameters in graphs, Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics, 46(2014) 281–288.
• [6] Cockayne, E.J. , Dreyer, P.A. , Hedetniemi, S.M. , Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics 278(2004) 11–22.
• [7] Hao, G. , Volkmann, L. , Mojdeh, D.A., Total double Roman domination in graphs, Communications in Combinatorics and Optimization 1(2020) 27–39 DOI: 10.22049/CCO.2019.26484.1118.
• [8] Haynes, T.W. , Hedetniemi, S.T. , Slater, P.J. , Fundamentals of Domination in graphs, New York: Marcel Dekker, (1998).
• [9] Henning, M.A., A characterization of Roman trees, Discussiones Mathematicae Graph Theory, 22(2002) 325–334.
• [10] Klostermeyer, W.F. , Mynhardt, C. M. , Protecting a graph with mobile guards, Appl. Anal. Discrete Math, 10(2016) 1–29.
• [11] Lewis, J.R. , Dierentials of graphs, Master’s Thesis, East Tennessee State University, (2004).
• [12] Mojdeh, D.A. , Mansourim, Zh. , On the Independent Double Roman Domination in Graphs, Bulletin of the Iranian Mathematical Society, https://doi.org/10.1007/s41980-019-00300-9.
• [13] Mojdeh, D.A. , Parsian, A. , Masoumi, I. , Characterization of double Roman trees, Ars combinatoria, (2018) to appear.
• [14] ReVelle, C.S., Can you protect the Roman Empire? Johns Hopkins Magazine 50(2)(1997).
• [15] ReVelle, C.S. , Rosing, K.E. , Defendens imperium romanum: a classical problem in military strategy, American Mathematical Monthly, 107(7)(2000) 585–594.
• [16] Stewart, I. , Defend the Roman empire!, Scientific American, 281(6)(1999), 136–139.
• [17] West, D.B. , Introduction to Graph theory, Second edition, Prentice Hall, (2001).