Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

Ograniczanie wyników

Czasopisma help

  1. 49 Discussiones Mathematicae Graph Theory

  2. 1 Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

  3. 1 International Journal of Applied Mathematics and Computer Science

Autorzy help

  1. 6 Henning M. A.

  2. 6 Volkmann L.

  3. 5 Haynes T.

  4. 4 Mynhardt C.

  5. 3 Harant J.

Więcej...
Lata help

  1. 4 2018

  2. 6 2016

  3. 2 2015

  4. 2 2013

  5. 4 2012

Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 52

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

Wyniki wyszukiwania

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

help Ogranicz wyniki do:
first rewind previous Strona / 3 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination Subdivision Numbers

100%
Haynes T., Hedetniemi S., Hedetniemi S., Jacobs D., Knisely J., van der Merwe L.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
239-253
EN
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with unique minimum total dominating sets

100%
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
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A note on domination in bipartite graphs

100%
Gerlach T., Harant J.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
229-231
EN
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On dominating the Cartesian product of a graph and K₂

100%
Hartnell B., Rall D.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
389-402
EN
In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated further.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some remarks on α-domination

100%
Dahme F., Rautenbach D., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
423-430
EN
Let α ∈ (0,1) and let $G = (V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D ⊆ V_G$ is called an α-dominating set of G, if $|N_G(u) ∩ D| ≥ αd_G(u)$ for all $u ∈ V_G∖D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On domination in graphs

100%
Göring F., Harant J.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
7-12
EN
For a finite undirected graph G on n vertices two continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the domination number γ of G. An efficient approximation method is developed and known upper bounds on γ are slightly improved.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination and independence subdivision numbers of graphs

80%
Haynes T., Hedetniemi S., Hedetniemi S.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
271-280
EN
The domination subdivision number $sd_γ(G)$ of a graph 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. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices in G. We then define the independence subdivision number $sd_β(G)$ to equal the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the independence number. We show that for any graph G of order n ≥ 2, either $G = K_{1,m}$ and $sd_β(G) = m$, or $1 ≤ sd_β(G) ≤ 2$. We also characterize the graphs G for which $sd_β(G) = 2$.
8
Content available remote

A Characterization of Trees for a New Lower Bound on the K-Independence Number

80%
Meddah N., Blidia M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
395-410
EN
Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. The maximum cardinality of a k-independent set of G is the k-independence number βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv are the chromatic number, the number of supports vertices and the number of leaves neighbors of v, in the graph G, respectively. Moreover, we characterize extremal trees attaining these bounds.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Paired-domination

80%
Fitzpatrick S., Hartnell B.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
63-72
EN
We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of girth seven or more of this type.
10
Content available remote

On Graphs with Disjoint Dominating and 2-Dominating Sets

80%
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.
11
Content available remote

Bipartition Polynomials, the Ising Model, and Domination in Graphs

80%
Dod M., Kotek T., Preen J., Tittmann P.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
335-353
EN
This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph invariants. We apply this approach to show that, analogously to the Tutte polynomial, the Ising polynomial introduced by Andrén and Markström in [3], can be represented as a sum over spanning forests.
12
Content available remote

A Characterization of Hypergraphs with Large Domination Number

80%
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.
13
Content available remote

Optimal Locating-Total Dominating Sets in Strips of Height 3

80%
Junnila V.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
447-462
EN
A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V \ C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012). In particular, they have determined the sizes of the smallest locating-total dominating sets in the finite strips of height 2 for all lengths. Moreover, they state as open question the analogous problem for the strips of height 3. In this paper, we answer the proposed question by determining the smallest sizes of locating-total dominating sets in the finite strips of height 3 as well as the smallest density in the infinite strip of height 3.
14
Content available remote

Power Domination in Knödel Graphs and Hanoi Graphs

80%
Varghese S., Vijayakumar A., Hinz A. M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
63-74
EN
In this paper, we study the power domination problem in Knödel graphs WΔ,2ν and Hanoi graphs [...] Hpn $H_p^n $ . We determine the power domination number of W3,2ν and provide an upper bound for the power domination number of Wr+1,2r+1 for r ≥ 3. We also compute the k-power domination number and the k-propagation radius of [...] Hp2 $H_p^2$ .
15
Content available remote

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

80%
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.
16
Content available remote

A Note on Non-Dominating Set Partitions in Graphs

80%
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.
17
Content available remote

Bounding the Openk-Monopoly Number of Strong Product Graphs

80%
Kuziak D., Peterin I., Yero I. G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
287-299
EN
Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ {1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋} be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $\delta _M (v) \ge {{\delta _G (v)} \over 2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we study the open k-monopoly number of strong product graphs. We present general lower and upper bounds for the open k-monopoly number of strong product graphs. Moreover, we study in addition the open 0-monopolies of several specific families of strong product graphs.
18
Content available remote

Hereditary Equality of Domination and Exponential Domination

80%
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.
19
Content available remote

Weak and exact domination in distributed systems

80%
Afifi L., Magri E. M., El Jai A.
International Journal of Applied Mathematics and Computer Science
|
2010
|
tom 20
|
nr 3
419-426
EN
In this work, we introduce and examine the notion of domination for a class of linear distributed systems. This consists in studying the possibility to make a comparison between input or output operators. We give the main algebraic properties of such relations, as well as characterizations of exact and weak domination. We also study the case of actuators, and various situations are examined. Applications and illustrative examples are also given. By duality, we extend this study to observed systems. We obtain similar results and properties, and the case of sensors is equally examined.
20
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Hereditary domination and independence parameters

80%
Goddard W., Haynes T., Knisley D.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
239-248
EN
For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.
first rewind previous Strona / 3 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ć.