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: 8

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

Wyniki wyszukiwania

help Sortuj według:

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

On Graphs with Disjoint Dominating and 2-Dominating Sets

100%
Henning M. A., Rall D. F.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
139-146
EN
A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.
2
Content available remote

Domination Game: Extremal Families for the 3/5-Conjecture for Forests

100%
Henning M. A., Löwenstein C.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 2
369-381
EN
In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107] posted their 3/5-Conjecture that γg(G) ≤ ⅗n for every isolate-free forest on n vertices. Brešar, Klavžar, Košmrlj and Rall [Discrete Appl. Math. 161 (2013) 1308-1316] presented a construction that yields an infinite family of trees that attain the conjectured 3/5-bound. In this paper, we provide a much larger, but simpler, construction of extremal trees. We conjecture that if G is an isolate-free forest on n vertices satisfying γg(G) = ⅗n, then every component of G belongs to our construction.
3
Content available remote

A Characterization of Hypergraphs with Large Domination Number

100%
Henning M. A., Löwenstein C.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
427-438
EN
Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V \ D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all edges of size at least k and with no isolated vertex, then γ(H) ≤ (n + ⌊(k − 3)/2⌋m)/(⌊3(k − 1)/2⌋). In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.
4
Content available remote

Bounds On The Disjunctive Total Domination Number Of A Tree

100%
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.
5
Content available remote

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

100%
Henning M. A., Marcon A. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
71-93
EN
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.
6
Content available remote

A Note on Non-Dominating Set Partitions in Graphs

81%
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
Content available remote

Domination Parameters of a Graph and its Complement

81%
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.
8
Content available remote

Hereditary Equality of Domination and Exponential Domination

81%
Henning M. A., Jäger S., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
275-285
EN
We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.
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ć.