Total Roman \2\-domination in graphs

DOI10.2989/16073606.2019.1695230zbMATH Open1462.05274arXiv2101.02537OpenAlexW3119727685MaRDI QIDQ4986532FDOQ4986532

Authors: Suitberto Cabrera García, Abel Cabrera Martínez, F. A. Hernández-Mira, Ismael G. Yero 

Publication date: 27 April 2021

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

Abstract: Given a graph $G=(V,E)$, a function $f:Vightarrow0,1,2$ is a total Roman $2$-dominating function if: (1) every vertex $vinV$ for which $f(v)=0$ satisfies that $su{m}_{uinN(v)}f(u)geq2$, where $N(v)$ represents the open neighborhood of $v$, and (2) every vertex $xinV$ for which $f(x)geq1$ is adjacent to at least one vertex $yinV$ such that $f(y)geq1$. The weight of the function $f$ is defined as $omega(f)=su{m}_{vinV}f(v)$. The total Roman $2$-domination number, denoted by $gamm{a}_{tR2}(G)$, is the minimum weight among all total Roman $2$-dominating functions on $G$. In this article we introduce the concepts above and begin the study of its combinatorial and computational properties. For instance, we give several closed relationships between this parameter and other domination related parameters in graphs. In addition, we prove that the complexity of computing the value $gamm{a}_{tR2}(G)$ is NP-hard, even when restricted to bipartite or chordal graphs.

Full work available at URL: https://arxiv.org/abs/2101.02537

Recommendations

• Total Roman \(\{2\}\)-dominating functions in graphs
• Algorithmic and complexity aspects of problems related to total Roman domination for graphs
• Roman \(\{2 \}\)-domination
• Total roman domination in graphs
• On the total Roman domination stability in graphs

zbMATH Keywords

total dominationRoman \(\{2\}\)-dominationtotal Roman \(\{2\}\)-dominationtotal Roman domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Roman \(\{2 \}\)-domination
• Some remarks on domination
• Total domination in graphs
• A survey of selected recent results on total domination in graphs
• Construction of trees and graphs with equal domination parameters
• Roman domination on strongly chordal graphs
• Title not available (Why is that?)
• Dominating Sets in Chordal Graphs
• Total Roman domination in graphs
• On Double Domination in Graphs
• Independent and double domination in trees
• Italian domination in trees
• Title not available (Why is that?)
• On the total Roman domination in trees
• Total Roman domination in the lexicographic product of graphs

Cited In (18)

• Total Roman domination for proper interval graphs
• Title not available (Why is that?)
• Total Roman domination in the lexicographic product of graphs
• Relating the total \(\{2\}\)-domination number with the total domination number of graphs
• Note on 2-rainbow domination and Roman domination in graphs
• Hop total Roman domination in graphs
• Difference between 2-rainbow domination and roman domination in graphs
• Total Roman \(\{2\}\)-reinforcement of graphs
• Further progress on the total Roman \(\{2\}\)-domination number of graphs
• Total Roman reinforcement in graphs
• Quasi-total Roman domination in graphs
• From \(w\)-domination in graphs to domination parameters in lexicographic product graphs
• On 2-rainbow domination and roman domination in graphs
• Algorithmic aspects of total Roman ${2}$-domination in graphs
• From Italian domination in lexicographic product graphs to w-domination in graphs
• Title not available (Why is that?)
• Independent Roman \(\{2 \}\)-domination in graphs
• Algorithmic aspect on total Roman \(\{2\}\)-domination of Cartesian products of paths and cycles

This page was built for publication: Total Roman \(\{2\}\)-domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986532)