Online citations, reference lists, and bibliographies.

Computational Complexity Of Outer-Independent Total And Total Roman Domination Numbers In Trees

Z. Li, Zehui Shao, Fangnian Lang, Xiaosong Zhang, Jia-Bao Liu
Published 2018 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
An outer-independent total dominating set (OITDS) of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$ , and the set $V(G)\setminus D$ is independent. The outer-independent total domination number of a graph $G$ , denoted by $\gamma _{oit}(G)$ , is the minimum cardinality of an OITDS of $G$ . An outer-independent total Roman dominating function (OITRDF) on a graph $G$ is a function $f: V(G) \rightarrow \{0, 1, 2\}$ satisfying the conditions that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$ , every vertex $x$ with $f(x)\geq 1$ is adjacent to at least one vertex $y$ with $f(y)\geq 1$ , and any two different vertices $a,b$ with $f(a)=f(b)=0$ are not adjacent. The minimum weight $\omega (f) =\sum _{v\in V(G)}f(v)$ of any OITRDF $f$ for $G$ is the outer-independent total Roman domination number of $G$ , denoted by $\gamma _{oitR}(G)$ . A graph $G$ is called an outer-independent total Roman graph (OIT-Roman graph) if $\gamma _{oitR}(G)=2\gamma _{oit}(G)$ . In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph.
This paper references
10.1093/comjnl/bxy038
On Computational and Combinatorial Properties of the Total Co-independent Domination Number of Graphs
Abel Cabrera Martínez (2019)
10.1007/s00373-014-1415-3
Global Roman Domination in Trees
M. Atapour (2015)
10.1016/J.DAM.2018.12.018
Outer-independent total Roman domination in graphs
Abel Cabrera Martínez (2019)
10.2298/AADM160802017A
Total Roman domination in graphs
H. Abdollahzadeh (2016)
10.2298/AADM151112023C
LOWER BOUNDS ON THE ROMAN AND INDEPENDENT ROMAN DOMINATION NUMBERS
M. Chellali (2016)
Total outer-independent domination in graphs
Marcin Krzywkowski (2014)
10.1016/j.dam.2015.11.013
Roman {2}-domination
M. Chellali (2016)
10.1137/070699688
Extremal Problems for Roman Domination
Erin W. Chambers (2009)
10.1016/j.dam.2016.03.004
Strong equality of Roman and weak Roman domination in trees
José D. Alvarado (2016)
and S
Z. Shao (2018)
10.1016/j.dam.2017.07.026
On the signed Roman k-domination: Complexity and thin torus graphs
Zehui Shao (2017)
10.1016/S0012-365X(02)00811-7
Defending the Roman Empire--A new strategy
M. Henning (2003)
and L
M. Atapour (2015)
and G
N. D. Soner (2012)
10.1136/bmj.323.7325.1375/a
I and i
K. Barraclough (2001)
10.1136/bjo.46.11.704
A and V
R. Stephenson (1962)
10.1016/j.crma.2010.11.021
A lower bound on the total outer-independent domination number of a tree
Marcin Krzywkowski (2011)
and D
E. W. Chambers (2009)
and S
M. Chellali (2016)
10.1080/00207160.2017.1301437
Outer independent Roman dominating functions in graphs
H. Ahangar (2017)
10.1016/b978-0-12-384931-1.00016-7
P
J. Lackie (2013)



This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar