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 20
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ł:
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ł:
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ł:
Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Autorzy:
Henning, Michael A.
Marcon, Alister J.
Powiązania:
https://bibliotekanauki.pl/articles/31341173.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
semitotal domination
trees
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 71-93
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Graphs with Disjoint Dominating and 2-Dominating Sets
Autorzy:
Henning, Michael A.
Rall, Douglas F.
Powiązania:
https://bibliotekanauki.pl/articles/30146715.pdf
Data publikacji:
2013-03-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
2-domination
vertex partition
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 139-146
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hereditary Equality of Domination and Exponential Domination
Autorzy:
Henning, Michael A.
Jäger, Simon
Rautenbach, Dieter
Powiązania:
https://bibliotekanauki.pl/articles/31342424.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
exponential domination
hereditary class
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 275-285
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds On The Disjunctive Total Domination Number Of A Tree
Autorzy:
Henning, Michael A.
Naicker, Viroshan
Powiązania:
https://bibliotekanauki.pl/articles/31341124.pdf
Data publikacji:
2016-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total domination
disjunctive total domination
trees
Opis:
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, $ \gamma_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, $ \gamma_t^d (G) $, is the minimum cardinality of such a set. We observe that $ \gamma_t^d (G) \ge \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 $ \mathcal{l} $ leaves and $s$ support vertices, then $ 2(n−\mathcal{l}+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 $ \gamma_t(T) // \gamma_t^d (T) <2 $ and this bound is asymptotically tight.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 1; 153-171
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Accurate Domination in Graphs
Autorzy:
Cyman, Joanna
Henning, Michael A.
Topp, Jerzy
Powiązania:
https://bibliotekanauki.pl/articles/31343372.pdf
Data publikacji:
2019-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
accurate domination number
tree
corona
Opis:
A dominating set of a graph G is a subset D ⊆ VG such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. The accurate domination number of G, denoted by γa(G), is the cardinality of a smallest set D that is a dominating set of G and no |D|-element subset of VG \ D is a dominating set of G. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees G for which γa(G) = γ(G) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 615-627
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Restrained Domination in Self-Complementary Graphs
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/32083901.pdf
Data publikacji:
2021-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
complement
restrained domination
self-complementary graph
Opis:
A self-complementary graph is a graph isomorphic to its complement. A set S of vertices in a graph G is a restrained dominating set if every vertex in V(G) \ S is adjacent to a vertex in S and to a vertex in V(G) \ S. The restrained domination number of a graph G is the minimum cardinality of a restrained dominating set of G. In this paper, we study restrained domination in self-complementary graphs. In particular, we characterize the self-complementary graphs having equal domination and restrained domination numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 633-645
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Independent Domination in Planar Cubic Graphs
Autorzy:
Abrishami, Gholamreza
Henning, Michael A.
Rahbarnia, Freydoon
Powiązania:
https://bibliotekanauki.pl/articles/31343229.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independent domination number
domination number
cubic graphs
Opis:
A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i(G)$, of $G$ is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if \( G \not\in \{ K_{3,3}, C_5 \square K_2 \} \) is a connected, cubic graph on $n$ vertices, then $i(G) \le 3/8 n $, where $ C_5 \square K_2 $ is the 5-prism. As an application of known result, we observe that this conjecture is true when $G$ is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if $G$ is a bipartite, planar, cubic graph of order $n$, then $ i(G) \le 1/3 n $, and we provide an infinite family of such graphs that achieve this bound.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 841-853
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Non-Dominating Set Partitions in Graphs
Autorzy:
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/31340558.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
total domination
non-dominating partition
nontotal dominating partition
Opis:
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 $ \overline{G} $ and the minimum number of sets in a non-total dominating set partition of $G$ equals the domination number of $ \overline{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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 1043-1050
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Characterization of Hypergraphs with Large Domination Number
Autorzy:
Henning, Michael A.
Löwenstein, Christian
Powiązania:
https://bibliotekanauki.pl/articles/31340924.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
transversal
hypergraph
Opis:
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 \subseteq V $ such that for every vertex $ v \in V \ \backslash \ D $ there exists an edge $ \mathcal{e} \in E $ for which $ v \in \mathcal{e} $ and $ \mathcal{e} \cap D \ne \emptyset $. The domination number $ \gamma (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 \ge 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 $ \gamma (H) \ge (n + \floor{ (k − 3)//2 } m) // ( \floor{ 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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 427-438
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on Domination Parameters in Graphs: A Brief Survey
Autorzy:
Henning, Michael A.
Powiązania:
https://bibliotekanauki.pl/articles/32313552.pdf
Data publikacji:
2022-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bounds
domination parameters
Opis:
In this paper we present a brief survey of bounds on selected domination parameters. We focus primarily on bounds on domination parameters in terms of the order and minimum degree of the graph. We present a list of open problems and conjectures that have yet to be solved in the hope of attracting future researchers to the field.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 665-708
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Semitotal Domination Problem in Block Graphs
Autorzy:
Henning, Michael A.
Pal, Saikat
Pradhan, D.
Powiązania:
https://bibliotekanauki.pl/articles/32361741.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
semitotal domination
block graphs
undirected path graphs
NP-complete
Opis:
A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 231-248
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 20

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