Roman domination excellent graphs: trees

Document Type : Original paper

Author

University of Architecture, Civil Еngineering and Geodesy; Department of Mathematics

Abstract

A Roman dominating function (RDF) on a graph $G = (V, E)$ is a labeling $f : V \rightarrow \{0, 1, 2\}$ such that every vertex with label $0$ has a neighbor with label $2$. The weight of $f$ is the value $f(V) = \Sigma_{v\in V} f(v)$ The Roman domination number, $\gamma_R(G)$, of $G$ is the minimum weight of an RDF on $G$. An RDF of minimum weight is  called a $\gamma_R$-function. A graph G is said to be $\gamma_R$-excellent if for each vertex $x \in V$ there is a $\gamma_R$-function $h_x$ on $G$ with $h_x(x) \neq 0$. We present a constructive characterization of $\gamma_R$-excellent trees using labelings. A graph $G$ is said to be in class $UVR$ if $\gamma(G-v) = \gamma (G)$ for each $v \in V$, where $\gamma(G)$ is the domination number of $G$. We show that each tree in $UVR$ is $\gamma_R$-excellent.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M.A. Henning, C. L¨owenstein, Y. Zhao, and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), no. 2, 241–255.
[2] T. Burton and D.P. Sumnur, γ-excellent, critically dominated, end-dominated, and dot-critical trees are equivalent, Discrete Math. 307 (2007), no. 6, 683–693.
[3] E.W. Chambers, B. Kinnerslay, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575–1586.
[4] E.J. Cockayne, P.A. Jr. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1, 11–22.
[5] J. Dunbar, S.T. Hedetniemi, M.A. Henning, and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics and Applications (Y. Alavi and A. Schwenk, eds.), Wiley, 1995, pp. 311–321.
[6] J. Dunbar, S.T. Hedetniemi, and A. McRae, Minus domination in graphs, Discrete Math. 199 (1999), no. 1-3, 35–47.
[7] G. Fricke, T. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and R. Laskar, Excellent trees, Bull. Inst. Comb. Appl. 34 (2002), 27–38.
[8] A. Hansberg, N.J. Rad, and L. Volkmann, Vertex and edge critical Roman domination in graphs, Util. Math. 92 (2013), 73–97.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
[10] T.W. Haynes and M.A. Henning, A characterization of i-excellent trees, Discrete Math. 248 (2002), no. 1-3, 69–77.
[11] , Changing and unchanging domination: a classification, Discrete Math. 272 (2003), no. 1, 65–79.
[12] M.A. Henning, Total domination excellent trees, Discrete Math. 263 (2003), no. 1-3, 93–104.
[13] E.M. Jackson, Explorations in the classification of vertices as good or bad, Mas ter’s thesis, East Tennessee State University, 8 2001.
[14] V. Samodivkin, Domination in graphs, God. Univ. Arkhit. Stroit. Geod. Sofiya, Svitk II, Mat. Mekh. 39 (1996-1997), 111–135.
[15] V. Samodivkin, The bondage number of graphs: good and bad vertices, Discuss. Math. Graph Theory 28 (2008), no. 3, 453–462.
[16] T. Trotter, Partially ordered sets, Handbook of Combinatorics (Y. Alavi and A. Schwenk, eds.), Elsevier, 1995, pp. 433–480.
Communications in Combinatorics and Optimization
Volume 3, Issue 1
June 2018
Pages 1-24

Files

Share

How to cite

Statistics