Paper Info
Title
Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees
Abstract
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)\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) -> {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) >= 1 is adjacent to at least one vertex y with f(y) >= 1, and any two different vertices a, b with f(a) = f(b) = 0 are not adjacent. The minimum weight omega(f) = Sigma(v is an element of 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.
Year
DOI
Venue
2018
10.1109/ACCESS.2018.2851972
IEEE ACCESS
Keywords
Field
DocType
Outer-independent total domination,outer-independent total Roman domination,outer-independent total Roman graph,tree,algorithm
Dominating set,Combinatorics,Vertex (geometry),Computer science,Cardinality,Computer network,Omega,Minimum weight,Domination analysis,Time complexity,Computational complexity theory
Journal
Volume
ISSN
Citations 
6
2169-3536
0
PageRank 
References 
Authors
0.34
4
5
Name
Order
Citations
PageRank
Zepeng Li100.68
Zehui Shao211930.98
Fangnian Lang311.04
Xiao-song Zhang430545.10
Jia-Bao Liu511021.86