Results 31 to 40 of about 43,787 (293)
Blocking total dominating sets via edge contractions
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.
Esther Galby, Felix Mann, Bernard Ries
openaire +4 more sources
Bounds on the Locating-Domination Number and Differentiating-Total Domination Number in Trees
Discussiones Mathematicae Graph Theory, 2018 A subset S of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V − S has a neighbor in S, and is a total dominating set if every vertex in V has a neighbor in S.
Rad Nader Jafari, Rahbani Hadi
doaj +1 more source
Secure total domination in chain graphs and cographs
AKCE International Journal of Graphs and Combinatorics, 2020 Let G = (V,E) be a graph without isolated vertices. A subset D of vertices of G is called a total dominating set of G if for every there exists a vertex such that A total dominating set D of a graph G is called a secure total dominating set of G if for ...
Anupriya Jha
doaj +1 more source
Computing locating-total domination number in some rotationally symmetric graphs
Science Progress, 2021 Let G = ( V , E ) be a connected graph. A locating-total dominating set in a graph G is a total dominating set S of a G , for every pair of vertices i , j ∈ V ( G ) ∖ S , such that N ( i ) ∩ S ≠ N ( j ) ∩ S .
Hassan Raza +3 more
doaj +1 more source
Vertices contained in all or in no minimum total dominating set of a tree [PDF]
, 2003 A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. We characterize the set of vertices of a tree that are contained in all, or in no, minimum total dominating sets of the ...
Cockayne, Ernest J. +2 more
core +1 more source
Edge Dominating Sets and Vertex Covers
Discussiones Mathematicae Graph Theory, 2013 Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering ...
Dutton Ronald, Klostermeyer William F.
doaj +1 more source
Total Dominating Sets and Total Domination Polynomials of Square Of Paths
IOSR Journal of Mathematics, 2014 Let G= ( V , E ) be a simple connected graph. A set S V is a total dominating set of G if every vertex is adjacent to an element of S. Let Dt(Wn ,i) be the family of all total dominating sets of the graph Wn , n ≥ 3 with cardinality i, and let dt (Wn ,i) = │Dt (Wn 2 , i) │. In this paper we compute dt(Wn ,i),and obtain the polynomial Dt(Wn , x) = dt(Wn
T. Premala, C. Sekar
openaire +1 more source
Total Roman {2}-Dominating Functions in Graphs [PDF]
, 2022 A Roman {2}-dominating function (R2F) is a function f : V → {0, 1, 2} with the property that for every vertex v ∈ V with f(v) = 0 there is a neighbor u of v with f(u) = 2, or there are two neighbors x, y of v with f(x) = f(y) = 1.
Chellali, M. +3 more
core +1 more source
Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach [PDF]
, 2022 In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set (MTDS) problem. We propose a new idea to compute approximate MDS and MTDS. This new approach can be implemented in a distributed model or parallel model.
Alipour, Sharareh, Salari, Mohammadhadi
core +1 more source
Algorithmic complexity of secure connected domination in graphs
AKCE International Journal of Graphs and Combinatorics, 2020 Let be a simple, undirected, and connected graph. A connected (total) dominating set is a secure connected (total) dominating set of G, if for each there exists such that and is a connected (total) dominating set of G. The minimum cardinality of a secure
J. Pavan Kumar +2 more
doaj +1 more source