Results 1 to 10 of about 40,947 (146)
A Linear Kernel for Planar Total Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when ...
Valentin Garnero, Ignasi Sau
doaj +4 more sources
Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set [PDF]
Opuscula MathematicaA graph \(G\) whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. We give constructions that yield infinite families of graphs that are TI-graphs, as well as constructions that yield ...
Teresa W. Haynes, Michael A. Henning
doaj +2 more sources
Augmenting graphs to partition their vertices into a total dominating set and an independent dominating set [PDF]
Opuscula MathematicaA graph \(G\) whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We define the TI-augmentation number \(\operatorname{ti}(
Teresa W. Haynes, Michael A. Henning
doaj +3 more sources
Optimal Locating-Total Dominating Sets in Strips of Height 3
Discussiones Mathematicae Graph Theory, 2015 A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V \ C the subsets formed
Junnila Ville
doaj +4 more sources
Blocking total dominating sets via edge contractions [PDF]
Theoretical Computer Science, 2021 In this paper, we study the problem of deciding whether the total domination number of a given graph $G$ can be reduced using exactly one edge contraction (called 1-Edge Contraction($ _t$)). We focus on several graph classes and determine the computational complexity of this problem.
Galby, Esther +2 more
openaire +3 more sources
Some results on the open locating-total domination number in graphs [PDF]
Journal of Mahani Mathematical Research, 2023 In this paper, we generalize the concept of an open locating-dominating set in graphs. We introduce a concept as an open locating-total dominating set in graphs that is equivalent to the open neighborhood locating-dominating set.
Fateme Movahedi, Mohammad Hadi Akhbari
doaj +1 more source
More on the Enumeration of Some Kind of Dominating Sets in Cactus Chains [PDF]
Mathematics Interdisciplinary Research, 2022 A non-empty set S ⊆ V is a dominating set, if every vertex not in S is adjacent to at least one vertex in S, and S is a total dominating set, if every vertex of V is adjacent to some vertices of S.
Somayeh Jahari, Saeid Alikhani
doaj +1 more source
Disjoint total dominating sets in near‐triangulations
Journal of Graph Theory, 2023 AbstractWe show that every simple planar near‐triangulation with minimum degree at least three contains two disjoint total dominating sets. The class includes all simple planar triangulations other than the triangle. This affirms a conjecture of Goddard and Henning.
P. Francis +3 more
openaire +2 more sources
A linear-time algorithm to compute total $[1,2]$-domination number of block graphs [PDF]
AUT Journal of Mathematics and Computing, 2020 Let $G=(V, E)$ be a simple graph without isolated vertices. A set $D\subseteq V$ is a total $[1,2]$-dominating set if for every vertex $v\in V , 1\leq |N(v)\cap D|\leq 2$.
Pouyeh Sharifani +2 more
doaj +1 more source
Nordhaus-Gaddum bounds for upper total domination [PDF]
Opuscula Mathematica, 2022 A set \(S\) of vertices in an isolate-free graph \(G\) is a total dominating set if every vertex in \(G\) is adjacent to a vertex in \(S\). A total dominating set of \(G\) is minimal if it contains no total dominating set of \(G\) as a proper subset. The
Teresa W. Haynes, Michael A. Henning
doaj +1 more source