Disjunctive total domination in permutation graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Let [Formula: see text] be a graph with vertex set [Formula: see text] and edge set [Formula: see text]. If [Formula: see text] has no isolated vertex, then a disjunctive total dominating set (DTD-set) of [Formula: see text] is a vertex set [Formula: see text] such that every vertex in [Formula: see text] is adjacent to a vertex of [Formula: see text] or has at least two vertices in [Formula: see text] at distance two from it, and the disjunctive total domination number [Formula: see text] of [Formula: see text] is the minimum cardinality overall DTD-sets of [Formula: see text]. Let [Formula: see text] and [Formula: see text] be two disjoint copies of a graph [Formula: see text], and let [Formula: see text] be a bijection. Then, a permutation graph [Formula: see text] has the vertex set [Formula: see text] and the edge set [Formula: see text]. For any connected graph [Formula: see text] of order at least three, we prove the sharp bounds [Formula: see text]; we give an example showing that [Formula: see text] can be arbitrarily large. We characterize permutation graphs for which [Formula: see text] holds. Further, we show that [Formula: see text] when [Formula: see text] is a cycle, a path, and a complete [Formula: see text]-partite graph, respectively.
