A Constructive Characterization of Vertex Cover Roman Trees

Discussiones Mathematicae Graph Theory

Kuziak Dorota¹  Yero Ismael G.²  Martínez Abel Cabrera³ 

[1] Universidad de Cádiz, Departamento de Estadística e Investigación, Operativa, Escuela Politécnica Superior de Algeciras, Av. Ramón Puyol s/n, 11202Algeciras, Spain;Universidad de Cádiz, Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras, Av. Ramón Puyol s/n, 11202Algeciras, Spain;Universitat Rovira i Virgili, Departament d'Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007Tarragona, Spain;

关键词: roman domination;    outer-independent roman domination;    vertex cover;    vertex independence;    trees;    05c69;    05c05;    05c75;   

DOI  :  10.7151/dmgt.2179

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown