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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 46
Tytuł:
Connected odd dominating sets in graphs
Autorzy:
Caro, Yair
Klostermeyer, William
Yuster, Raphael
Powiązania:
https://bibliotekanauki.pl/articles/744351.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
odd dominating set
Opis:
An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 225-239
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on the Locating-Total Domination in Graphs
Autorzy:
Miller, Mirka
Rajan, R. Sundara
Jayagopal, R.
Rajasingh, Indra
Manuel, Paul
Powiązania:
https://bibliotekanauki.pl/articles/31341658.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
total dominating set
locating-dominating set
locating-total dominating set
regular graphs
Opis:
In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 745-754
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Making a Dominating Set of a Graph Connected
Autorzy:
Li, Hengzhe
Wu, Baoyindureng
Yang, Weihua
Powiązania:
https://bibliotekanauki.pl/articles/31342251.pdf
Data publikacji:
2018-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
independent set
dominating set
connected dominating set
Opis:
Let $ G = (V,E) $ be a graph and $ S \subseteq V $. We say that $ S $ is a dominating set of $ G $, if each vertex in $ V \backlash S $ has a neighbor in $S$. Moreover, we say that $S$ is a connected (respectively, 2-edge connected or 2-connected) dominating set of $G$ if $ G[S] $ is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of $G$ is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of $G$, and is denoted $ \gamma (G) $ (respectively $ \gamma_1 (G) $, or $ \gamma_2^′ (G) $, or $ \gamma_2 (G) $). A well-known result of Duchet and Meyniel states that $ \gamma_1 (G) \le 3 \gamma (G) − 2 $ for any connected graph $G$. We show that if $ \gamma (G) \ge 2 $, then $ \gamma_2^′ (G) \ge 5 \gamma (G) − 4 $ when $G$ is a 2-edge connected graph and $ \gamma_2 (G) \le 11 \gamma (G) − 13 $ when $G$ is a 2-connected triangle-free graph.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 947-962
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Odd and residue domination numbers of a graph
Autorzy:
Caro, Yair
Klostermeyer, William
Goldwasser, John
Powiązania:
https://bibliotekanauki.pl/articles/743442.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
odd dominating set
parity domination
Opis:
Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 119-136
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Eternal Domination: Criticality and Reachability
Autorzy:
Klostermeyer, William F.
MacGillivray, Gary
Powiązania:
https://bibliotekanauki.pl/articles/31342174.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
eternal dominating set
critical graphs
Opis:
We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs and tight bounds on connectivity, edge-connectivity and diameter are given. It is also shown that there exist graphs in which deletion of any edge increases the eternal domination number, and graphs in which addition of any edge decreases the eternal domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 63-77
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hereditary Equality of Domination and Exponential Domination in Subcubic Graphs
Autorzy:
Chen, Xue-Gang
Wang, Yu-Feng
Wu, Xiao-Fei
Powiązania:
https://bibliotekanauki.pl/articles/32324524.pdf
Data publikacji:
2021-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
exponential dominating set
subcubic graphs
Opis:
Let γ(G) and γe(G) denote the domination number and exponential domination number of graph G, respectively. Henning et al., in [Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 275–285] gave a conjecture: There is a finite set ℱ of graphs such that a graph G satisfies (H) = γe(H) for every induced subgraph H of G if and only if G is ℱ-free. In this paper, we study the conjecture for subcubic graphs. We characterize the class ℱ by minimal forbidden induced subgraphs and prove that the conjecture holds for subcubic graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1067-1075
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Independent transversal domination in graphs
Autorzy:
Hamid, Ismail
Powiązania:
https://bibliotekanauki.pl/articles/743635.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
independent set
independent transversal dominating set
Opis:
A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by $γ_{it}(G)$. In this paper we begin an investigation of this parameter.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 1; 5-17
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Quasiperfect domination in triangular lattices
Autorzy:
Dejter, Italo
Powiązania:
https://bibliotekanauki.pl/articles/743129.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
perfect dominating set
quasiperfect dominating set
triangular lattice
Opis:
A vertex subset S of a graph G is a perfect (resp. quasiperfect) dominating set in G if each vertex v of G∖S is adjacent to only one vertex ($d_v$ ∈ {1,2} vertices) of S. Perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol {3,6} and in its toroidal quotients are investigated, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form $K_ν$, where ν ∈ {1,2,3} depends only on S.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 179-198
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Locating-Domination Number and Differentiating-Total Domination Number in Trees
Autorzy:
Rad, Nader Jafari
Rahbani, Hadi
Powiązania:
https://bibliotekanauki.pl/articles/31342324.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
locating-dominating set
differentiating-total dominating set
tree
Opis:
A subset $S$ of vertices in a graph $G = (V,E)$ is a dominating set of $G$ if every vertex in $V − S$ has a neighbor in $S$, and is a total dominating set if every vertex in $V$ has a neighbor in $S$. A dominating set $S$ is a locating-dominating set of $G$ if every two vertices $ x, y \in V − S$ satisfy $N(x) \cap S \ne N(y) \cap S$. The locating-domination number $ \gamma_L (G) $ is the minimum cardinality of a locating-dominating set of $G$. A total dominating set $S$ is called a differentiating-total dominating set if for every pair of distinct vertices $u$ and $v$ of $G$, $ N[u] \cap S \ne N[v] \cap S $. The minimum cardinality of a differentiating-total dominating set of $G$ is the differentiating-total domination number of $G$, denoted by $ \gamma_t^D (G) $. We obtain new upper bounds for the locating-domination number, and the differentiating-total domination number in trees. Moreover, we characterize all trees achieving equality for the new bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 455-462
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination, Eternal Domination, and Clique Covering
Autorzy:
Klostermeyer, William F.
Mynhardt, C.M.
Powiązania:
https://bibliotekanauki.pl/articles/31339487.pdf
Data publikacji:
2015-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
eternal dominating set
independent set
clique cover
Opis:
Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 283-300
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On minimum intersections of certain secondary dominating sets in graphs
Autorzy:
Kosiorowska, Anna
Michalski, Adrian
Włoch, Iwona
Powiązania:
https://bibliotekanauki.pl/articles/29519420.pdf
Data publikacji:
2023
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating set
2-dominating set
(1, 2)-dominating set
proper (1, 2)-dominating set
domination number
(1,2)-intersection index
Opis:
In this paper we consider secondary dominating sets, also named as (1,k)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the (1, 1)-dominating sets and proper (1, 2)-dominating sets. We introduce (1,2̅)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
Źródło:
Opuscula Mathematica; 2023, 43, 6; 813-827
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Edge Dominating Sets and Vertex Covers
Autorzy:
Dutton, Ronald
Klostermeyer, William F.
Powiązania:
https://bibliotekanauki.pl/articles/30146532.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge dominating set
matching
total dominating set
vertex cover
Opis:
Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 437-456
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dominating Vertex Covers: The Vertex-Edge Domination Problem
Autorzy:
Klostermeyer, William F.
Messinger, Margaret-Ellen
Yeo, Anders
Powiązania:
https://bibliotekanauki.pl/articles/32083812.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cubic graph
dominating set
vertex cover
vertex-edge dominating set
Opis:
The vertex-edge domination number of a graph, γve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γve(G) = γ(G) for bipartite graph G.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A characterization of roman trees
Autorzy:
Henning, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743366.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
Roman dominating function
Opis:
A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is $w(f) = ∑_{v ∈ V} f(v)$. The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called Roman graphs. At the Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications held at Western Michigan University in June 2000, Stephen T. Hedetniemi in his principal talk entitled "Defending the Roman Empire" posed the open problem of characterizing the Roman trees. In this paper, we give a characterization of Roman trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 2; 325-334
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Bounds on the Locating-Total Domination Number in Trees
Autorzy:
Wang, Kun
Ning, Wenjie
Lu, Mei
Powiązania:
https://bibliotekanauki.pl/articles/31867549.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
tree
total dominating set
locating-total dominating set
locating-total domination number
Opis:
Given a graph $G = (V, E)$ with no isolated vertex, a subset $S$ of $V$ is called a total dominating set of $G$ if every vertex in $V$ has a neighbor in $S$. A total dominating set $S$ is called a locating-total dominating set if for each pair of distinct vertices $u$ and $v$ in $V \ S, N(u) ∩ S ≠ N(v) ∩ S$. The minimum cardinality of a locating-total dominating set of $G$ is the locating-total domination number, denoted by $γ_t^L(G)$. We show that, for a tree $T$ of order $n ≥ 3$ and diameter $d$, \(\frac{d+1}{2}≤γ_t^L(T)≤n−\frac{d−1}{2}\), and if $T$ has $l$ leaves, $s$ support vertices and $s_1$ strong support vertices, then \(γ_t^L(T)≥max\Big\{\frac{n+l−s+1}{2}−\frac{s+s_1}{4},\frac{2(n+1)+3(l−s)−s_1}{5}\Big\}\). We also characterize the extremal trees achieving these bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 25-34
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 46

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