Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 15

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  total domination
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Two Short Proofs on Total Domination

100%
Bickle A.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
457-459
EN
A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph Υt (G) is the minimum size of a total dominating set. We provide a short proof of the result that Υt (G) ≤ 2/3n for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with unique minimum total dominating sets

63%
Haynes T., Henning M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
233-246
EN
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.
3
Content available remote

Characterization of Cubic Graphs G with irt(G) = Irt(G) = 2

51%
Eslahchi C., Haghi S., Jafari N.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
559-565
EN
A subset S of vertices in a graph G is called a total irredundant set if, for each vertex v in G, v or one of its neighbors has no neighbor in S −{v}. The total irredundance number, ir(G), is the minimum cardinality of a maximal total irredundant set of G, while the upper total irredundance number, IR(G), is the maximum cardinality of a such set. In this paper we characterize all cubic graphs G with irt(G) = IRt(G) = 2
4
Content available remote

Cubic Graphs with Total Domatic Number at Least Two

51%
Akbari S., Motiei M., Mozaffari S., Yazdanbod S.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
75-82
EN
Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.
5
Content available remote

Bounds On The Disjunctive Total Domination Number Of A Tree

51%
Henning M. A., Naicker V.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
153-171
EN
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $\gamma _t^d (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G) $\gamma _t^d (G) \le \gamma _t (G)$ . A leaf of G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. We show that if T is a tree of order n with ℓ leaves and s support vertices, then [...] 2(n−ℓ+3)/5≤γtd(T)≤(n+s−1)/2 $2(n - \ell + 3)/5 \le \gamma _t^d (T) \le (n + s - 1)/2$ and we characterize the families of trees which attain these bounds. For every tree T, we show have [...] γt(T)/γtd(T)<2 $\gamma _t (T)/\gamma _t^d (T) < 2$ and this bound is asymptotically tight.
6
Content available remote

A Note on Non-Dominating Set Partitions in Graphs

51%
Desormeaux W. J., Haynes T. W., Henning M. A.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
1043-1050
EN
A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on domination parameters in random graphs

51%
Bonato A., Wang C.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
335-343
EN
Domination parameters in random graphs G(n,p), where p is a fixed real number in (0,1), are investigated. We show that with probability tending to 1 as n → ∞, the total and independent domination numbers concentrate on the domination number of G(n,p).
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Secure domination and secure total domination in graphs

51%
Klostermeyer W., Mynhardt C.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
267-284
EN
A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-{x}) ∪ {u}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_{st}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{st}(G) ≤ γ_s(G)$. We also show that $γ_{st}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A characterization of (γₜ,γ₂)-trees

51%
Lu Y., Hou X., Xu J.-M., Li N.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
425-435
EN
Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some results on total domination in direct products of graphs

45%
Dorbec P., Gravier S., Klavžar S., Spacapan S.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
103-112
EN
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partitioning a graph into a dominating set, a total dominating set, and something else

45%
Henning M., Löwenstein C., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
563-574
EN
A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination versus paired domination

45%
Schaudt O.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
435-447
EN
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/Δ.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination in categorical products of graphs

45%
Rall D.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
35-44
EN
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.
14
Content available remote

On the Complexity of Reinforcement in Graphs

38%
Rad N. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
877-887
EN
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.
15
Content available remote

Domination Parameters of a Graph and its Complement

38%
Desormeaux W. J., Haynes T. W., Henning M. A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
203-215
EN
A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.