Trees with vertex-edge Roman Domination number twice the domination number minus one

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-2020-06-0084

Keywords:

Vertex-edge roman dominating set, Dominating set, Branch duplication in trees

Abstract

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.

Author Biographies

H. Naresh Kumar, Sastra University.

Dept. of Mathematics, School of Arts, Science and Humanities.

Y. B. Venkatakrishnan, Sastra University.

Dept. of Mathematics, School of Arts, Science and Humanities.

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

2020-11-12

How to Cite

[1]
H. Naresh Kumar and Y. B. Venkatakrishnan, “Trees with vertex-edge Roman Domination number twice the domination number minus one”, Proyecciones (Antofagasta, On line), vol. 39, no. 6, pp. 1381-1392, Nov. 2020.

Issue

Section

Artículos