Filtry
wszystkich: 93
Wyniki wyszukiwania dla: dominating set

Polynomial Algorithm for Minimal (1,2)Dominating Set in Networks
PublikacjaDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NPhard. In this paper, we...

Super Dominating Sets in Graphs
PublikacjaIn this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.

On proper (1,2)‐dominating sets in graphs
PublikacjaIn 2008, Hedetniemi et al. introduced the concept of (1,)domination and obtained some interesting results for (1,2) domination. Obviously every (1,1) dominating set of a graph (known as 2dominating set) is (1,2) dominating; to distinguish these concepts, we define a proper (1,2) dominating set of a graph as follows: a subset is a proper (1,2) dominating set of a graph if is (1,2) dominating and it is not a (1,1) dominating...

Minimal 2dominating sets in Trees
PublikacjaWe provide an algorithm for listing all minimal 2dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2dominating sets. We also show that thisbound is tight.

Minimal double dominating sets in trees
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.

Reconfiguring Minimum Dominating Sets in Trees
PublikacjaWe provide tight bounds on the diameter of γgraphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γgraph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple lineartime algorithm for determining...

Trees having many minimal dominating sets
PublikacjaWe provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...

An Algorithm for Listing All Minimal 2Dominating Sets of a Tree
PublikacjaWe provide an algorithm for listing all minimal 2dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2dominating sets. We also show that this bound is tigh.

An algorithm for listing all minimal double dominating sets of a tree
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.

Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublikacjaSmart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a twoway communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....

Unicyclic graphs with equal total and total outerconnected domination numbers
PublikacjaLet G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...

Total Domination Versus Domination in Cubic Graphs
PublikacjaA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

On the ratio between 2domination and total outerindependent domination numbers of trees
PublikacjaA 2dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D. A total outerindependent dominating set 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 2domination (total outerindependent domination, respectively) number of a graph G is the minimum cardinality of a 2dominating (total...

On trees with double domination number equal to 2outerindependent domination number plus one
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G=(V,E), a subset D subseteq V(G) is a 2dominating set if every vertex of V(G)D has at least two neighbors...

Weakly connected Roman domination in graphs
PublikacjaA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...

On trees with equal 2domination and 2outerindependent domination numbers
PublikacjaFor a graph G = (V,E), a subset D \subseteq V(G) is a 2dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2outerindependent dominating set if additionally the set V(G)\D is independent. The 2domination (2outerindependent domination, respectively) number of G, is the minimum cardinality of a 2dominating (2outerindependent dominating, respectively) set of G. We characterize all trees...

On trees with equal domination and total outerindependent domination numbers
PublikacjaFor a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outerindependent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outerindependent domination, respectively) number of G is the minimum cardinality of a dominating (total outerindependent dominating, respectively) set of G. We characterize...

Graphs with equal domination and certified domination numbers
PublikacjaA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...

On trees with double domination number equal to total domination number plus one
PublikacjaA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...

On trees with double domination number equal to 2domination number plus one
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A subset D subseteq V(G) is a 2dominating set of G if every vertex of V(G)D is dominated by at least two vertices of D, while it is a double dominating set of G if every vertex of G is dominated by at least two vertices of D. The 2domination (double domination, respectively) number of a graph G is the minimum cardinality of a 2dominating (double dominating,...

The convex domination subdivision number of a graph
PublikacjaLet G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V  D has at least one neighbor in D. The distance d_G(u, v) between two vertices u and v is the length of a shortest (u, v)path in G. An (u, v)path of length d_G(u; v) is called an (u, v)geodesic. A set X\subset V is convex in G if vertices from all (a, b)geodesics belong to X for any two vertices a, b \in X. A set X is a convex dominating...

Total domination in versus paireddomination in regular graphs
PublikacjaA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paireddominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

Weakly convex domination subdivision number of a graph
PublikacjaA set X is weakly convex in G if for any two vertices a; b \in X there exists an ab–geodesic such that all of its vertices belong to X. A set X \subset V is a weakly convex dominating set if X is weakly convex and dominating. The weakly convex domination number \gamma_wcon(G) of a graph G equals the minimum cardinality of a weakly convex dominating set in G. The weakly convex domination subdivision number sd_wcon (G) is the minimum...

Global defensive sets in graphs
PublikacjaIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if  N [ X ] ∩ S  ≥  N [ X ] \ S  holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...

Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublikacjaA vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...

A lower bound on the total outerindependent domination number of a tree
PublikacjaA total outerindependent dominating set 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 total outerindependent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outerindependent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n2l+2)/3,...

An upper bound on the 2outerindependent domination number of a tree
PublikacjaA 2outerindependent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2outerindependent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2outerindependent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2,...

An upper bound on the total outerindependent domination number of a tree
PublikacjaA total outerindependent dominating set of a graph G=(V(G),E(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 total outerindependent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outerindependent dominating set of G. We prove that for every tree T of order n >= 4, with l leaves and s support vertices we have...

An upper bound for the double outerindependent domination number of a tree
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double outerindependent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)\D is independent. The double outerindependent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outerindependent dominating set of G. We prove...

2outerindependent domination in graphs
PublikacjaWe initiate the study of 2outerindependent domination in graphs. A 2outerindependent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D, and the set V(G)\D is independent. The 2outerindependent domination number of a graph G is the minimum cardinality of a 2outerindependent dominating set of G. We show that if a graph has minimum degree at least two,...

An Alternative Proof of a Lower Bound on the 2Domination Number of a Tree
PublikacjaA 2dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2dominating set of G. Fink and Jacobson [ndomination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283300] established the following lower bound on the 2domination...

Bounds on the vertexedge domination number of a tree
PublikacjaA vertexedge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertexedge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertexedge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(nls+3)/4...

On trees attaining an upper bound on the total domination number
PublikacjaA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paireddomination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 6975] established the following upper bound on the total domination...

Paired domination versus domination and packing number in graphs
PublikacjaGiven a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a kpacking in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The kpacking number is the order of a largest kpacking and...

All graphs with paireddomination number two less than their order
PublikacjaLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paireddominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paireddomination number γp(G) of G is defined to be the minimum cardinality of a paireddominating set of G. Let G be a graph of order n. In [Paireddomination in graphs, Networks 32 (1998), 199206] Haynes and Slater...

A lower bound on the double outerindependent domination number of a tree
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double outerindependent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outerindependent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outerindependent dominating set of G. We...

Weakly convex and convex domination numbers of some products of graphs
PublikacjaIf $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(ab)$ path is called a $(uv)${\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(ab)$ geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(ab)$geodesic belong to $X$. The {\it weakly convex domination number}...

Independent Domination Subdivision in Graphs
PublikacjaA set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each...

Isolation Number versus Domination Number of Trees
PublikacjaIf G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G)....

Bipartite theory of graphs: outerindependent domination
PublikacjaLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$adjacent if they have a common neighbor in $Y$, and they are $X$independent otherwise. A subset $D \subseteq X$ is an $X$outerindependent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$independent. The $X$outerindependent domination number...

DominationRelated Parameters in Rooted Product Graphs
PublikacjaAbstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several dominationrelated parameters in rooted product graphs.

2bondage in graphs
PublikacjaA 2dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2dominating set of G. The 2bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(GE') > gamma_2(G). If for every E' subseteq E we have...

On the super domination number of lexicographic product graphs
PublikacjaThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...

Double bondage in graphs
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...

Nonisolating bondage in graphs
PublikacjaA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The nonisolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(GE') \ge 1$ and $\gamma(GE')...

Nonisolating 2bondage in graphs
PublikacjaA 2dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2dominating set of G. The nonisolating 2bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(GE') >= 1 and gamma_2(GE') > gamma_2(G)....

Certified domination
PublikacjaImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...

Complexity Issues on of Secondary Domination Number
PublikacjaIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...

Common Independence in Graphs
PublikacjaAbstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with X...

INFLUENCE OF A VERTEX REMOVING ON THE CONNECTED DOMINATION NUMBER – APPLICATION TO ADHOC WIRELESS NETWORKS
PublikacjaA minimum connected dominating set (MCDS) can be used as virtual backbone in adhoc wireless networks for efficient routing and broadcasting tasks. To find the MCDS is an NP complete problem even in unit disk graphs. Many suboptimal algorithms are reported in the literature to find the MCDS using local information instead to use global network knowledge, achieving an important reduction in complexity. Since a wireless network...