Trees with vertex-edge Roman Domination number twice the domination number minus one
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-06-0084Keywords:
Vertex-edge roman dominating set, Dominating set, Branch duplication in treesAbstract
A vertex-edge Roman dominating function (or just ve-RDF) of a graph G = (V, E) is a function f : V (G) → {0, 1, 2} such that for each edge e = uv either max{f (u), f (v)} ≠ 0 or there exists a vertex w such that either wu ∈ E or wv ∈ E and f (w) = 2. The weight of a ve-RDF is the sum of its function values over all vertices. The vertex-edge Roman domination number of a graph G, denoted by γ veR(G), is the minimum weight of a ve-RDF G. We characterize trees with vertexedge roman domination number equal to twice domination number minus one.
References
H. A. Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S. M, heikholeslami, “Trees with double roman domination number twice the domination number plus two”, Iranian journal of science and technology, transactions A: Science volume, vol. 43, pp. 1081–1088, Jun. 2019, doi: 10.1007/s40995-018-0535-7
R. Boutrig, M. Chellali, T. W. Haynes, and S. T. Hedetniemi, “Vertex-edge domination in graphs”, Aequationes mathematicae, vol. 90, no. 2, pp. 355–366, May 2015., doi: 10.1007/s00010-015-0354-2
M. Chellali and N. J. Rad, “Trees with unique Roman dominating functions of minimum weight”, Discrete mathematics, algorithms and applications, vol. 06, no. 03, Art ID 1450038, Jun. 2014., doi: 10.1142/S1793830914500384
E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, and S. T. Hedetniemi, “Roman domination in graphs”, Discrete mathematics, vol. 278, no. 1-3, pp. 11–22, Mar. 2004, doi: 10.1016/j.disc.2003.06.004
B. Krishnakumari, Y. B. Venkatakrishnan, and M. Krzywkowski, “Bounds on the vertex–edge domination number of a tree”, Comptes rendus mathematique, vol. 352, no. 5, pp. 363–366, May 2014, doi: 10.1016/j.crma.2014.03.017
J. R. Lewis, S. T. Hedetniemi, T. W. Haynes, and G. H. Fricke, “Vertex-edge domination”, Utilitas mathematica, vol. 81, pp. 193-213, 2010.
J. W. Peters, “Theoretical and algorithmic results on domination and connectivity”, Ph. D. Thesis, Clemson University, 1986. [On line]. Available: https://bit.ly/34lu9SS
P. R. L. Pushpam and S. Padmapriea, “Global Roman domination in graphs”, Discrete applied mathematics, vol. 200, pp. 176–185, Feb. 2016, doi: 10.1016/j.dam.2015.07.014
E. N. Satheesh, “Some variations of domination and applications”, Ph. D. Thesis, Mahatma Gandhi University, 2014. [On line]. Available: https://bit.ly/2HvoErI
X. Zhang, Z. Li, H. Jiang, and Z. Shao, “Double Roman domination in trees”, Information processing letters, vol. 134, pp. 31–34, Jun. 2018, doi: 10.1016/j.ipl.2018.01.004
Published
How to Cite
Issue
Section
Copyright (c) 2020 H. Naresh Kumar, Y. B. Venkatakrishnan
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.