Número de dominação romana e número de dominação romana independente para classes de grafos snarks

Abstract

Given a graph G = (V(G),E(G)), a function f : V(G) → {0,1,2} is a Roman Domination Function (RDF) of G if every vertex v ∈ V(G) with f(v) = 0 is adjacent to at least one vertex u with f(u) = 2. The weight of f , denoted by ω(f), is defined as: ω(f) = ∑v∈V(G) f(v). The Roman domination number of G is the smallest value ω(f) among all the RDFs f of G and is denoted by γR(G). There exists a variant of Roman domination in graphs, called independent Roman domination. A function f is called independent Roman domination function(IRDF) if f is an RDF and the union of the sets of vertices with labels 1 and 2 induces an independent set in G. Several results in the literature present limits for γR(G) or determine the value of γR(G) for some classes of graph. The class of cubic graphs is a class of interest in Graph Theory because many problems in graphs remain NP-complete for this class. A relevant subclass of cubic graphs are snarks graphs. A snark is a cubic graph that does not contain a cut edge and does not have a proper edge coloring with 3 colors. The parameter γR(G) was determined for the family of snarks flower graphs, but it remains not determined for other families of snarks. In this text, we present upper and lower bounds for γR(G) and iR(G) of Loupekine Snarks, we present an upper bound for γR(G) and iR(G) of Goldberg Snarks and we determine the exact value of γR(G) and iR(G) of generalized Blanuša snarks.