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ę "DOMINATION" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 328
Tytuł:
Domination Parameters of a Graph and its Complement
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31342430.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
complement
total domination
connected domination
clique domination
restrained domination
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 203-215
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Domination Versus Paired-Domination in Regular Graphs
Autorzy:
Cyman, Joanna
Dettlaff, Magda
Henning, Michael A.
Lemańska, Magdalena
Raczek, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/31342314.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
paired-domination
Opis:
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 minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 573-586
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Vertices belonging to all or to no minimum locating dominating sets of trees
Autorzy:
Blidia, M.
Lounes, R.
Powiązania:
https://bibliotekanauki.pl/articles/255510.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
locating domination
Opis:
A set D of vertices in a graph G is a locating-dominating set if for every two vertices u, v of G \ D the sets N(u) ∩ D and N (v) ∩ D are non-empty and different. In this paper, we characterize vertices that are in all or in no minimum locating dominating sets in trees. The characterization guarantees that the γL-excellent tree can be recognized in a polynomial time.
Źródło:
Opuscula Mathematica; 2009, 29, 1; 5-14
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs with equal domination and certified domination numbers
Autorzy:
Dettlaff, Magda
Lemańska, Magdalena
Miotk, Mateusz
Topp, Jerzy
Ziemann, Radosław
Żyliński, Paweł
Powiązania:
https://bibliotekanauki.pl/articles/255932.pdf
Data publikacji:
2019
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
certified domination
Opis:
A set D of vertices of a graph G = (VG, EG) is a dominating set of G if every vertex in VG — D is adjacent to at least one vertex in D. The domination number (upper domination number, respectively) of G, denoted by [formula], respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of G. A subset D ⊆ VG is called a certified dominating set of G if D is a dominating set of G and every vertex in D has either zero or at least two neighbors in VG — D. The cardinality of a smallest (largest minimal, respectively) certified dominating set of G is called the certified (upper certified, respectively) domination number of G and is denoted by [formula]), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.
Źródło:
Opuscula Mathematica; 2019, 39, 6; 815-827
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees with unique minimum total dominating sets
Autorzy:
Haynes, Teresa
Henning, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743354.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 233-246
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets
Autorzy:
Henning, Michael A.
Topp, Jerzy
Powiązania:
https://bibliotekanauki.pl/articles/32222686.pdf
Data publikacji:
2021-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
paired-domination
Opis:
A subset D ⊆ VG is a dominating set of G if every vertex in VG – D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP -graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP -graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459–467; J. Comb. Optim. 22 (2011) 217–234]. In this paper, we provide conditions which ensure that a graph is a DPDP -graph. In particular, we characterize the minimal DPDP -graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 827-847
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some remarks on α-domination
Autorzy:
Dahme, Franz
Rautenbach, Dieter
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/744557.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
α-domination
domination
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 423-430
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A remark on the (2,2)-domination number
Autorzy:
Korneffel, Torsten
Meierling, Dirk
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743033.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
distance domination number
p-domination number
Opis:
A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k,p}(G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k,p}(G) ≤ (p/(p+k))n(G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers k and p for the case that p is a multiple of k. In this paper we show that $γ_{2,2}(G) ≤ (n(G)+1)/2$ for all connected graphs G and characterize all connected graphs with $γ_{2,2} = (n+1)/2$. This means that for k = p = 2 we characterize all connected graphs for which the conjecture is true without the precondition that δ₂ ≥ 3.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 2; 361-366
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Characterization of block graphs with equal 2-domination number and domination number plus one
Autorzy:
Hansberg, Adriana
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743677.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
2-domination
multiple domination
block graph
Opis:
Let G be a simple graph, and let p be a positive integer. A subset D ⊆ V(G) is a p-dominating set of the graph G, if every vertex v ∈ V(G)-D is adjacent with at least p vertices of D. The p-domination number γₚ(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination number γ(G).
If G is a nontrivial connected block graph, then we show that γ₂(G) ≥ γ(G)+1, and we characterize all connected block graphs with γ₂(G) = γ(G)+1. Our results generalize those of Volkmann [12] for trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 93-103
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 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ł:
Paired-domination
Autorzy:
Fitzpatrick, S.
Hartnell, B.
Powiązania:
https://bibliotekanauki.pl/articles/744199.pdf
Data publikacji:
1998
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
paired-domination
matching
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 1998, 18, 1; 63-72
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graphs With Large Semipaired Domination Number
Autorzy:
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31343332.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
paired-domination
semipaired domination
Opis:
Let $G$ be a graph with vertex set $V$ and no isolated vertices. A subset $ S \subseteq V $ is a semipaired dominating set of $G$ if every vertex in $ V \backslash S $ is adjacent to a vertex in $S$ and $S$ can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number $ \gamma_{pr2}(G) $ is the minimum cardinality of a semipaired dominating set of $G$. We show that if $G$ is a connected graph $G$ of order $ n \ge 3 $, then \( \gamma_{pr2} (G) \le \tfrac{2}{3} n \), and we characterize the extremal graphs achieving equality in the bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 659-671
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on perfect k-domination in trees: an algorithmic approach
Autorzy:
Chaluvaraju, B.
Vidya, K. A.
Powiązania:
https://bibliotekanauki.pl/articles/255985.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
k-domination
perfect domination
perfect k-domination
Opis:
Let k be a positive integer and G = (V, E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G if every vertex v of G not in D is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k -dominating set of G is the perfect k-domination number γkp (G ). In this paper, a sharp bound for γkp (T) is obtained where T is a tree.
Źródło:
Opuscula Mathematica; 2012, 32, 4; 707-714
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on domination parameters in random graphs
Autorzy:
Bonato, Anthony
Wang, Changping
Powiązania:
https://bibliotekanauki.pl/articles/743019.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
random graphs
independent domination
total domination
Opis:
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).
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 2; 335-343
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 328

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