Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "total domination" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 66
Tytuł:
Domination parameters of a graph with added vertex
Autorzy:
Zwierzchowski, M.
Powiązania:
https://bibliotekanauki.pl/articles/2050876.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
total domination number
strong domination number
subdivision
Opis:
Let $G = (V, E)$ be a graph. A subset $D \subseteq V$ is a total dominating set of $G$ if for every vertex $y \in V$ there is a vertex $x \in D$ with $xy \in E$. A subset $D \subseteq V$ is a strong dominating set of G if for every vertex $y \in V - D$ there is a vertex $x \in D$ with $xy \in E and deg_{G}(x) \geq deg_{G}(y)$. The total domination number $\gamma_{t}(G)$ (the strong domination number $\gamma_{S}(G)$) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of $G$. The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [1], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [3]. By a subdivision of an edge $uv \in E$ we mean removing edge $uv$, adding a new vertex $x$, and adding edges $ux$ and $vx$. A graph obtained from $G$ by subdivision an edge $uv \in E$ is denoted by $G \oplus uxvx$. The behaviour of the total domination number and the strong domination number of a graph $G \oplus u_{x}v_{x}$ is developed.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 231-234
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Gallai-type equality for the total domination number of a graph
Autorzy:
Zhou, Sanming
Powiązania:
https://bibliotekanauki.pl/articles/744259.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
total domination number
Gallai equality
Opis:
We prove the following Gallai-type equality
γₜ(G) + εₜ(G) = p
for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 539-543
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Locating-Total Domination Number in Trees
Autorzy:
Wang, Kun
Ning, Wenjie
Lu, Mei
Powiązania:
https://bibliotekanauki.pl/articles/31867549.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
tree
total dominating set
locating-total dominating set
locating-total domination number
Opis:
Given a graph $G = (V, E)$ with no isolated vertex, a subset $S$ of $V$ is called a total dominating set of $G$ if every vertex in $V$ has a neighbor in $S$. A total dominating set $S$ is called a locating-total dominating set if for each pair of distinct vertices $u$ and $v$ in $V \ S, N(u) ∩ S ≠ N(v) ∩ S$. The minimum cardinality of a locating-total dominating set of $G$ is the locating-total domination number, denoted by $γ_t^L(G)$. We show that, for a tree $T$ of order $n ≥ 3$ and diameter $d$, \(\frac{d+1}{2}≤γ_t^L(T)≤n−\frac{d−1}{2}\), and if $T$ has $l$ leaves, $s$ support vertices and $s_1$ strong support vertices, then \(γ_t^L(T)≥max\Big\{\frac{n+l−s+1}{2}−\frac{s+s_1}{4},\frac{2(n+1)+3(l−s)−s_1}{5}\Big\}\). We also characterize the extremal trees achieving these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 25-34
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Signed Total Roman Domination in Digraphs
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31342127.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
signed total Roman dominating function
signed total Roman domination number
Opis:
Let $D$ be a finite and simple digraph with vertex set $V (D)$. A signed total Roman dominating function (STRDF) on a digraph $D$ is a function $ f : V (D) \rightarrow {−1, 1, 2} $ satisfying the conditions that (i) $ \Sigma_{x \in N^− (v) } f(x) \ge 1 $ for each $ v \in V (D) $, where $ N^− (v) $ consists of all vertices of $D$ from which arcs go into $v$, and (ii) every vertex u for which $f(u) = −1$ has an inner neighbor $v$ for which $f(v) = 2$. The weight of an STRDF $f$ is $ w(f) = \Sigma_{ v \in V } (D) f(v) $. The signed total Roman domination number $ \gamma_{stR} (D) $ of $D$ is the minimum weight of an STRDF on $D$. In this paper we initiate the study of the signed total Roman domination number of digraphs, and we present different bounds on $ \gamma_{stR} (D) $. In addition, we determine the signed total Roman domination number of some classes of digraphs. Some of our results are extensions of known properties of the signed total Roman domination number $ \gamma_{stR} (G)$ of graphs $G$.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 261-272
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Signed Total Roman k-Domatic Number Of A Graph
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31341581.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed total Roman k-dominating function
signed total Roman k-domination number
signed total Roman k-domatic number
Opis:
Let $ k \ge 1 $ be an integer. A signed total Roman $k$-dominating function on a graph $G$ is a function $ f : V (G) \rightarrow {−1, 1, 2} $ such that $ \Sigma_{ u \in N(v) } f(u) \ge k $ for every $ v \in V (G) $, where $ N(v) $ is the neighborhood of $ v $, and every vertex $ u \in V (G) $ for which $ f(u) = −1 $ is adjacent to at least one vertex w for which $ f(w) = 2 $. A set $ { f_1, f_2, . . ., f_d} $ of distinct signed total Roman $k$-dominating functions on $G$ with the property that $ \Sigma_{i=1}^d f_i(v) \le k $ for each $ v \in V (G) $, is called a signed total Roman $k$-dominating family (of functions) on $G$. The maximum number of functions in a signed total Roman $k$-dominating family on $G$ is the signed total Roman $k$-domatic number of $G$, denoted by $ d_{stR}^k (G) $. In this paper we initiate the study of signed total Roman $k$-domatic numbers in graphs, and we present sharp bounds for $ d_{stR}^k (G) $. In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed total Roman $k$-domatic number of some graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1027-1038
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Upper Bounds on the Signed Total (k, k)-Domatic Number of Graphs
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31339301.pdf
Data publikacji:
2015-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed total (k
k)-domatic number
signed total k-dominating function
signed total k-domination number
regular graphs
Opis:
Let $G$ be a graph with vertex set $V (G)$, and let $ f : V (G) \rightarrow {−1, 1}$ be a two-valued function. If $ k \geq 1$ is an integer and \( \sum_{ x \in N(v)} f(x) \geq k \) for each $ v \in V (G) $, where $N(v)$ is the neighborhood of $v$, then $f$ is a signed total $k$-dominating function on $G$. A set ${f_1, f_2, . . ., f_d}$ of distinct signed total k-dominating functions on $G$ with the property that \( \sum_{i=1}^d f_i(x) \leq k \) for each $ x \in V (G)$, is called a signed total ($k$, $k$)-dominating family (of functions) on $G$. The maximum number of functions in a signed total ($k$, $k$)-dominating family on $G$ is the signed total ($k$, $k$)-domatic number of $G$. In this article we mainly present upper bounds on the signed total ($k$, $k$)- domatic number, in particular for regular graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 4; 641-650
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Domination in Generalized Prisms and a New Domination Invariant
Autorzy:
Tepeh, Aleksandra
Powiązania:
https://bibliotekanauki.pl/articles/32222717.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
k -rainbow total domination
total domination
Opis:
In this paper we complement recent studies on the total domination of prisms by considering generalized prisms, i.e., Cartesian products of an arbitrary graph and a complete graph. By introducing a new domination invariant on a graph G, called the k-rainbow total domination number and denoted by γkrt(G), it is shown that the problem of finding the total domination number of a generalized prism G □ Kk is equivalent to an optimization problem of assigning subsets of {1, 2, . . ., k} to vertices of G. Various properties of the new domination invariant are presented, including, inter alia, that γkrt(G) = n for a nontrivial graph G of order n as soon as k ≥ 2Δ(G). To prove the mentioned result as well as the closed formulas for the k-rainbow total domination number of paths and cycles for every k, a new weight-redistribution method is introduced, which serves as an efficient tool for establishing a lower bound for a domination invariant.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1165-1178
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the total restrained domination number of direct products of graphs
Autorzy:
Shiu, Wai
Chen, Hong-Yu
Chen, Xue-Gang
Sun, Pak
Powiązania:
https://bibliotekanauki.pl/articles/743278.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination number
total restrained domination number
direct product of graphs
Opis:
Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by $γ_r^t(G)$, is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds are sharp by presenting some infinite families of graphs that attain these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 629-641
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The total {k}-domatic number of digraphs
Autorzy:
Sheikholeslami, Seyed
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743233.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
total {k}-dominating function
total {k}-domination number
total {k}-domatic number
Opis:
For a positive integer k, a total {k}-dominating function of a digraph D is a function f from the vertex set V(D) to the set {0,1,2, ...,k} such that for any vertex v ∈ V(D), the condition $∑_{u ∈ N^{ -}(v)}f(u) ≥ k$ is fulfilled, where N¯(v) consists of all vertices of D from which arcs go into v. A set ${f₁,f₂, ...,f_d}$ of total {k}-dominating functions of D with the property that $∑_{i = 1}^d f_i(v) ≤ k$ for each v ∈ V(D), is called a total {k}-dominating family (of functions) on D. The maximum number of functions in a total {k}-dominating family on D is the total {k}-domatic number of D, denoted by $dₜ^{{k}}(D)$. Note that $dₜ^{{1}}(D)$ is the classic total domatic number $dₜ(D)$. In this paper we initiate the study of the total {k}-domatic number in digraphs, and we present some bounds for $dₜ^{{k}}(D)$. Some of our results are extensions of well-know properties of the total domatic number of digraphs and the total {k}-domatic number of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 461-471
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total domination versus paired domination
Autorzy:
Schaudt, Oliver
Powiązania:
https://bibliotekanauki.pl/articles/743224.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
upper total domination
paired domination
upper paired domination
generalized claw-free graphs
Opis:
A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 435-447
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total domination in categorical products of graphs
Autorzy:
Rall, Douglas
Powiązania:
https://bibliotekanauki.pl/articles/744287.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
categorical product
open packing
total domination
submultiplicative
supermultiplicative
Opis:
Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the categorical product of graphs. In particular, we show that the total domination number of the categorical product of a nontrivial tree and any graph without isolated vertices is equal to the product of their total domination numbers. In the process we establish a packing and covering equality for trees analogous to the well-known result of Meir and Moon. Specifically, we prove equality between the total domination number and the open packing number of any tree of order at least two.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 35-44
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Complexity of Reinforcement in Graphs
Autorzy:
Rad, Nader Jafari
Powiązania:
https://bibliotekanauki.pl/articles/31340751.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
total restrained domination
p- domination
k-rainbow domination
reinforcement
NP-hard
Opis:
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 877-887
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees with equal restrained domination and total restrained domination numbers
Autorzy:
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/743684.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total restrained domination number
restrained domination number
trees
Opis:
For a graph G = (V,E), a set D ⊆ V(G) is a total restrained dominating set if it is a dominating set and both ⟨D⟩ and ⟨V(G)-D⟩ do not have isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. A set D ⊆ V(G) is a restrained dominating set if it is a dominating set and ⟨V(G)-D⟩ does not contain an isolated vertex. The cardinality of a minimum restrained dominating set in G is the restrained domination number. We characterize all trees for which total restrained and restrained domination numbers are equal.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 83-91
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The complexity of open k-monopolies in graphs for negative k
Autorzy:
Peterin, Iztok
Powiązania:
https://bibliotekanauki.pl/articles/255938.pdf
Data publikacji:
2019
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
open k-monopolies
complexity
total domination
Opis:
Let G be a graph with vertex set V(G), δ (G) minimum degree of G and [formula]. Given a nonempty set M ⊆ V(G) a vertex v of G is said to be k-controlled by M if [formula] where δM(v) represents the number of neighbors of v in M. The set M is called an open k-monopoly for G if it fc-controls every vertex v of G. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer k is NP-complete even restricted to chordal graphs.
Źródło:
Opuscula Mathematica; 2019, 39, 3; 425-431
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination and leaf density in graphs
Autorzy:
Pedersen, Anders
Powiązania:
https://bibliotekanauki.pl/articles/744357.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bounds
domination number
leaves
partioned domination
total domination number
Opis:
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for the total domination number and the partition domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 251-259
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 66

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies