Articles producció científica> Enginyeria Informàtica i Matemàtiques

Closed formulas for the total Roman domination number of lexicographic product graphs

  • Identification data

    Identifier: imarina:9232644
    Authors:
    Martinez, Abel CabreraRodriguez-Velazquez, Juan Alberto
    Abstract:
    Let G be a graph with no isolated vertex and f: V (G) -> {0, 1, 2} a function. Let V-i = {x is an element of V(G): f(x) = i} for every i is an element of {0, 1, 2}. We say that f is a total Roman dominating function on G if every vertex in V-0 is adjacent to at least one vertex in V-2 and the subgraph induced by V-1 boolean OR V-2 has no isolated vertex. The weight of f is omega(f) = Sigma(v is an element of V(G)) f (v). The minimum weight among all total Roman dominating functions on G is the total Roman domination number of G, denoted by gamma(tR)circle(G). It is known that the general problem of computing gamma(tR)(G) is NP-hard. In this paper, we show that if G is a graph with no isolated vertex and H is a nontrivial graph, then the total Roman domination number of the lexicographic product graph G circle H is given bygamma(tR)(G o H) = {2 gamma t(G) if gamma(H) >= 2,xi(G) if gamma(H) =1,where gamma(H) is the domination number of H, gamma(t)(G) is the total domination number of G and xi(G) is a domination parameter defined on G.
  • Others:

    Author, as appears in the article.: Martinez, Abel Cabrera; Rodriguez-Velazquez, Juan Alberto
    Department: Enginyeria Informàtica i Matemàtiques
    URV's Author/s: CABRERA MARTÍNEZ, ABEL / Rodríguez Velázquez, Juan Alberto
    Keywords: Total roman domination Total domination Lexicographic product graph
    Abstract: Let G be a graph with no isolated vertex and f: V (G) -> {0, 1, 2} a function. Let V-i = {x is an element of V(G): f(x) = i} for every i is an element of {0, 1, 2}. We say that f is a total Roman dominating function on G if every vertex in V-0 is adjacent to at least one vertex in V-2 and the subgraph induced by V-1 boolean OR V-2 has no isolated vertex. The weight of f is omega(f) = Sigma(v is an element of V(G)) f (v). The minimum weight among all total Roman dominating functions on G is the total Roman domination number of G, denoted by gamma(tR)circle(G). It is known that the general problem of computing gamma(tR)(G) is NP-hard. In this paper, we show that if G is a graph with no isolated vertex and H is a nontrivial graph, then the total Roman domination number of the lexicographic product graph G circle H is given bygamma(tR)(G o H) = {2 gamma t(G) if gamma(H) >= 2,xi(G) if gamma(H) =1,where gamma(H) is the domination number of H, gamma(t)(G) is the total domination number of G and xi(G) is a domination parameter defined on G.
    Thematic Areas: Theoretical computer science Mathematics, applied Mathematics Matemática / probabilidade e estatística Geometry and topology Discrete mathematics and combinatorics Algebra and number theory
    licence for use: https://creativecommons.org/licenses/by/3.0/es/
    Author's mail: juanalberto.rodriguez@urv.cat
    Author identifier: 0000-0002-9082-7647
    Record's date: 2024-10-26
    Papper version: info:eu-repo/semantics/publishedVersion
    Link to the original source: https://amc-journal.eu/index.php/amc/article/view/2284
    Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
    Papper original source: Ars Mathematica Contemporanea. 20 (2): 233-241
    APA: Martinez, Abel Cabrera; Rodriguez-Velazquez, Juan Alberto (2021). Closed formulas for the total Roman domination number of lexicographic product graphs. Ars Mathematica Contemporanea, 20(2), 233-241. DOI: 10.26493/1855-3974.2284.aeb
    Article's DOI: 10.26493/1855-3974.2284.aeb
    Entity: Universitat Rovira i Virgili
    Journal publication year: 2021
    Publication Type: Journal Publications
  • Keywords:

    Algebra and Number Theory,Discrete Mathematics and Combinatorics,Geometry and Topology,Mathematics,Mathematics, Applied,Theoretical Computer Science
    Total roman domination
    Total domination
    Lexicographic product graph
    Theoretical computer science
    Mathematics, applied
    Mathematics
    Matemática / probabilidade e estatística
    Geometry and topology
    Discrete mathematics and combinatorics
    Algebra and number theory
  • Documents:

  • Cerca a google

    Search to google scholar