Dominação romana dupla em grafos cúbicos

Abstract

Given a graph G, a function f : V(G) → {0,1,2,3} is called a double Roman domination function (DRDF) of G if, for every vertex v ∈V(G) with f(v) = 0, there exists at least one vertex u adjacent to v with f(u) = 3 or two vertices u1 e u2 adjacent to v with f(u1) = f(u2) = 2; and for every vertex v ∈ V(G) with f(v) = 1, there exists at least one vertex u adjacent to v with f(u) ∈ {2,3}. The weight of function f is defined by ω(f) = ∑v∈V(G) f(v). The double Roman domination number γdR(G) is the smallest weight ω(f) among all double Roman domination functions f of G. A DRDF that has the minimum weight in the graph G is called γdR-function. Cubic graphs are well studied in graph theory due to the fact that many graph problems become NP-complete when restricted to cubic graphs. In particular, a class of cubic graphs that is often considered is the class of snarks. A snark is a cubic graph, without bridges and with chromatic index equal to 4. In this work, we determine the double Roman domination number for the family of flower-snarks and generalized Blanuša snarks. In addition, we set upper and lower bounds for the double Roman domination number for Goldberg’s snarks and Loupekine’s snarks.