Vertex-Edge Roman Domination

Download PDF


DOI: 10.46793/KgJMat2105.685K


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. In this paper, we initiate a study of vertex-edge Roman dominaton. We first show that determining the number γveR(G) is NP-complete even for bipartite graphs. Then we show that if T is a tree different from a star with order n, l leaves and s support vertices, then γveR(T) (n l s + 3)2, and we characterize the trees attaining this lower bound. Finally, we provide a characterization of all trees with γveR(T) = 2γ(T), where γ(T) is the edge domination number of T.


Vertex-edge roman dominating set, edge dominating set, trees.


[1]   R. Boutrig, M. Chellali, T. W. Haynes and S. T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016), 355–366.

[2]   M. Chellali, T. W. Haynes and S. T. Hedetniemi, Bounds on weak Roman and 2-rainbow domination numbers, Discrete Appl. Math. 178 (2014), 27–32.

[3]   M. Chellali and N. Jafari Rad, Trees with unique Roman dominating functions of minimum weight, Discrete Math. Algorithms Appl. 6 (2014), Paper ID 1450038.

[4]   E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math. 78 (2004), 11–22.

[5]   B. Krishnakumari, Y. B. Venkatakrishnan and M. Krzywkowski, Bounds on the vertex-edge domination number of a tree, C. R. Math. Acad. Sci. Paris 352 (2014), 363–366.

[6]   J. R. Lewis, S. T. Hedetniemi, T. W. Haynes and G. H. Fricke, Vertex-edge domination, Util. Math. 81 (2010), 193–213.

[7]   S. Mitchell and S. T. Hedetniemi, Edge domination in trees, Congr. Numer. 19 (1977), 489–509.

[8]   K. W. Peters, Theoretical and algorithmic results on domination and connectivity, Ph.D. Thesis, Clemson University, 1986.

[9]   E. N. Satheesh, Some variations of domination and applications, Ph.D. Thesis, Mahatma Gandhi University, 2014.