# Wyniki wyszukiwania dla: domination - MOST Wiedzy

## Wyszukiwarka

Wyniki wyszukiwania dla: domination
• wyników na stronę:

wszystkich: 116

### Wyniki wyszukiwania dla: domination

• #### Paired domination and doubly domination in graphs

Publikacja

- Rok 2007

W rozprawie poruszane są zagadnienia związane z dominowaniem parami w grafach oraz domiowaniem totalno - powściągniętym w grafach. Ponadto omawiane są zagadnienia związane ze złożonością obliczeniową różnych problemów dominowania w grafach.

• #### Domination subdivision and domination multisubdivision numbers of graphs

Publikacja

- Rok 2019

The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)&lt;=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...

Pełny tekst do pobrania w portalu

• #### Graphs with equal domination and certified domination numbers

Publikacja

- Rok 2019

A 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...

Pełny tekst do pobrania w portalu

• #### Total Domination Versus Domination in Cubic Graphs

Publikacja

- Rok 2018

A 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...

Pełny tekst do pobrania w portalu

• #### Total domination in versus paired-domination in regular graphs

Publikacja

- Rok 2018

A 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 paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

Pełny tekst do pobrania w portalu

• #### The paired-domination and the upper paired-domination numbers of graphs

Publikacja

- Rok 2015

In this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.

Pełny tekst do pobrania w portalu

• #### Graphs with equal domination and 2-distance domination numbers

Publikacja

- Rok 2011

W publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.

Pełny tekst do pobrania w portalu

• #### Paired domination versus domination and packing number in graphs

Publikacja

- Rok 2022

Given 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 k-packing 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 k-packing number is the order of a largest kpacking and...

Pełny tekst do pobrania w portalu

• #### Certified domination

Publikacja

Imagine 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...

Pełny tekst do pobrania w portalu

• #### On trees with equal domination and total outer-independent domination numbers

Publikacja

- Rok 2015

For 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 outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...

• #### Trees with equal restrained domination and total restrained domination numbers

Publikacja

- Rok 2007

W publikacji scharakteryzowano wszystkie drzewa, w których liczby dominowania powściągniętego oraz podwójnie totalnego są sobie równe.

Pełny tekst do pobrania w portalu

Publikacja

For a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees... Pełny tekst do pobrania w portalu • #### On trees with double domination number equal to 2-domination number plus one Publikacja - Rok 2013 A vertex of a graph is said to dominate itself and all of its neighbors. A subset D subseteq V(G) is a 2-dominating 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 2-domination (double domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (double dominating,... Pełny tekst do pobrania w serwisie zewnętrznym • #### On the ratio between 2-domination and total outer-independent domination numbers of trees Publikacja - Rok 2013 A 2-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. A total outer-independent 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 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total... Pełny tekst do pobrania w serwisie zewnętrznym • #### On trees with double domination number equal to total domination number plus one Publikacja - Rok 2011 A 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,... Pełny tekst do pobrania w portalu • #### Independent Domination Subdivision in Graphs Publikacja - Rok 2021 A 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... Pełny tekst do pobrania w portalu • #### Secure Italian domination in graphs Publikacja - Rok 2021 An Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)&gt;0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating... Pełny tekst do pobrania w portalu • #### The limit case of a domination property Publikacja - Rok 2012 Praca dotyczy dolnego ograniczenia liczby dominowania w grafach, ze względu na ilość wierzchołków oraz największą liczbę liści w drzewie spinającym. Pełny tekst do pobrania w serwisie zewnętrznym • #### On trees with double domination number equal to 2-outer-independent domination number plus one Publikacja - Rok 2012 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 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 2-dominating set if every vertex of V(G)D has at least two neighbors... Pełny tekst do pobrania w serwisie zewnętrznym • #### 2-outer-independent domination in graphs Publikacja - Rok 2015 We initiate the study of 2-outer-independent domination in graphs. A 2-outer-independent 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 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,... Pełny tekst do pobrania w portalu • #### Coronas and Domination Subdivision Number of a Graph Publikacja In this paper, for a graph G and a family of partitions P of vertex neighborhoods of G, we deﬁne the general corona G ◦P of G. Among several properties of this new operation, we focus on application general coronas to a new kind of characterization of trees with the domination subdivision number equal to 3. Pełny tekst do pobrania w portalu • #### Interpolation properties of domination parameters of a graph Publikacja - Rok 2010 An integer-valued graph function π is an interpolating function if a set π(T(G))={π(T): T∈TT(G)} consists of consecutive integers, where TT(G) is the set of all spanning trees of a connected graph G. We consider the interpolation properties of domination related parameters. Pełny tekst do pobrania w portalu • #### On the connected and weakly convex domination numbers Publikacja In this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number... Pełny tekst do pobrania w portalu • #### On domination multisubdivision number of unicyclic graphs Publikacja - Rok 2018 The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with... Pełny tekst do pobrania w portalu • #### TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH Publikacja - Rok 2015 The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msd_t (G) of a graph G and we show that for any connected graph G of order at least two, msd_t (G) ≤ 3. We show that for trees the total domination... Pełny tekst do pobrania w portalu • #### Complexity Issues on of Secondary Domination Number Publikacja - Rok 2023 In 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... Pełny tekst do pobrania w portalu • #### The convex domination subdivision number of a graph Publikacja Let 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... Pełny tekst do pobrania w portalu • #### Weakly connected Roman domination in graphs Publikacja - Rok 2019 A 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... Pełny tekst do pobrania w portalu • #### On the total restrained domination number of a graph Publikacja - Rok 2006 W pracy przedstawione są ograniczenia i własności liczby dominowania podwójnie totalnego. Pełny tekst do pobrania w portalu • #### Total outer-connected domination in trees Publikacja - Rok 2010 W pracy przedstawiono dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego w grafach oraz scharakteryzowano wszystkie drzewa osiągające to ograniczenie. Pełny tekst do pobrania w portalu • #### Total restrained domination numbers of trees Publikacja - Rok 2008 Opisane są wszystkie drzewa, w których liczby dominowania totalnego i totalno - powściągniętego są sobie równe, a także podano dolne ograniczenie na liczbę dominowania totalno - powściągniętego w drzewach. Pełny tekst do pobrania w serwisie zewnętrznym • #### Distance paired domination numbers of graphs Publikacja - Rok 2008 W pracy przedstawione są pewne własności liczb k-dominowania parami w grafach. Wykazane jest, że problem decyzyjny liczby k-dominowania parami jest problemem NP-zupełnym nawet dla grafów dwudzielnych. Przedstawione są ograniczenia górne i dolne dla liczby k-dominowania parami w drzewach i scharakteryzowane drzewa, w których te ograniczenia są osiągnięte. Pełny tekst do pobrania w serwisie zewnętrznym • #### The outer-connected domination number of a graph Publikacja - Rok 2007 W pracy została zdefiniowana liczba dominowania zewnętrznie spójnego i przedstawiono jej podstawowe własności. Pełny tekst do pobrania w portalu • #### Weakly connected domination subdivision numbers Publikacja - Rok 2008 Liczba podziału krawędzi dla dominowania słabo spójnego to najmniejsza liczba krawędzi jaką należy podzielić, aby wzrosła liczba dominowania słabo wypukłego. W pracy przedstawione są własności liczby podziału krawędzi dla dominowania słabo spójnego dla różnych grafów. Pełny tekst do pobrania w portalu • #### Weakly connected domination critical graphs Publikacja - Rok 2008 Praca dotyczy niektórych klas grafów krytycznych ze względu na liczbę dominowania słabo spójnego. Pełny tekst do pobrania w portalu • #### Lower bound on the domination number of a tree. Publikacja - Rok 2004 W pracy przedstawiono dolne ograniczenie na liczbę dominowania w drzewach oraz przedstawiono pełną charakterystykę grafów ekstremalnych. • #### Weakly convex and convex domination numbers. Publikacja - Rok 2004 W artykule przedstawione są nowo zdefiniowane liczby dominowania wypukłego i słabo wypukłego oraz ich porównanie z innymi liczbami dominowania. W szczególności, rozważana jest równość liczby dominowania spójnego i wypukłego dla grafów kubicznych. • #### On the doubly connected domination number of a graph Publikacja - Rok 2006 W pracy została zdefiniowana liczba dominowania podwójnie spójnego i przedstawiono jej podstawowe własności. Pełny tekst do pobrania w portalu • #### Domination-Related Parameters in Rooted Product Graphs Publikacja Abstract 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 domination-related parameters in rooted product graphs. Pełny tekst do pobrania w serwisie zewnętrznym • #### Paired domination subdivision and multisubdivision numbers of graphs Publikacja The paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph... Pełny tekst do pobrania w portalu • #### Influence of edge subdivision on the convex domination number Publikacja - Rok 2012 We study the influence of edge subdivision on the convex domination number. We show that in general an edge subdivision can arbitrarily increase and arbitrarily decrease the convex domination number. We also find some bounds for unicyclic graphs and we investigate graphs G for which the convex domination number changes after subdivision of any edge in G. Pełny tekst do pobrania w portalu • #### Weakly convex domination subdivision number of a graph Publikacja - Rok 2016 A 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... Pełny tekst do pobrania w portalu • #### On the super domination number of lexicographic product graphs Publikacja - Rok 2019 The 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... Pełny tekst do pobrania w portalu • #### Bounds on the vertex-edge domination number of a tree Publikacja - Rok 2014 A vertex-edge 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 vertex-edge domination number of a graph$G$, denoted by$\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge 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$(n-l-s+3)/4...

Pełny tekst do pobrania w portalu

• #### Bipartite theory of graphs: outer-independent domination

Publikacja

- Rok 2015

Let $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$-outer-independent 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$-outer-independent domination number...

Pełny tekst do pobrania w serwisie zewnętrznym

• #### Isolation Number versus Domination Number of Trees

Publikacja
• M. Lemańska
• M. J. Souto-Salorio
• A. Dapena
• F. Vazquez-Araujo

- Rok 2021

If 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)....

Pełny tekst do pobrania w portalu

• #### Total outer-connected domination numbers of trees

Publikacja

- Rok 2009

Niech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...

Pełny tekst do pobrania w portalu

• #### Lower bound on the paired domination number of a tree

Publikacja

- Rok 2006

W pracy przedstawione jest ograniczenie dolne dla liczby dominowania parami oraz scharakteryzowane są wszystkie drzewa ekstremalne.

Pełny tekst do pobrania w portalu

• #### Strong weakly connected domination subdivisible graphs

Publikacja

- Rok 2010

Artykuł dotyczy wpływu podziału krawędzi na liczbę dominowania słabo spójnego. Charakteryzujemy grafy dla których podział dowolnej krawędzi zmienia liczbę dominowania słabo spójnego oraz grafy dla których podział dowolnych dwóch krawędzi powoduje zmianę liczby dominowania słabo spójnego.

Pełny tekst do pobrania w portalu

• #### Weakly connected domination stable trees [online]

Publikacja

- Rok 2009

Praca dotyczy pełnej charakteryzacji drzew stabilnych ze względu na liczbę dominowania słabo spójnego.

Pełny tekst do pobrania w serwisie zewnętrznym