Authors: A. Cabrera Martínez, D. Kuziak, I.G. Yero Title: A constructive characterization of vertex cover Roman trees Source: Discussiones Mathematicae Graph Theory Received 22.06.2017, Revised 05.10.2018, Accepted 05.10.2018, doi: 10.7151/dmgt.2179 | |
Abstract: A Roman dominating function on a graph G=(V(G),E(G)) is a function f : V(G)→ {0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The Roman dominating function f is an outer-independent Roman dominating function on G if the set of vertices labeled with zero under f is an independent set. The outer-independent Roman domination number γ_{oiR}(G) is the minimum weight w(f)=∑_{v∈V(G)}f(v) of any outer-independent Roman dominating function f of G. A vertex cover of a graph G is a set of vertices that covers all the edges of G. The minimum cardinality of a vertex cover is denoted by α(G). A graph G is a vertex cover Roman graph if γ_{oiR}(G)=2α(G). A constructive characterization of the vertex cover Roman trees is given in this article. | |
Keywords: Roman domination, outer-independent Roman domination, vertex cover, vertex independence, trees | |
Links: |