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ł:
γ-paired dominating graphs of cycles
Autorzy:
Eakawinrujee, Pannawat
Trakultraipruk, Nantapath
Powiązania:
https://bibliotekanauki.pl/articles/2048671.pdf
Data publikacji:
2022
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
paired dominating graph
paired dominating set
paired-domination number
Opis:
A paired dominating set of a graph G is a dominating set whose induced subgraph contains a perfect matching. The paired domination number, denoted by γpr(G), is the minimum cardinality of a paired dominating set of G. A γpr(G)-set is a paired dominating set of cardinality γpr(G). The γ-paired dominating graph of G, denoted by PDγ(G), as the graph whose vertices are γpr(G)-sets. Two γpr(G)-sets D1 and D2 are adjacent in PDγ(G) if there exists a vertex u ∈ D1 and a vertex v /∈ D1 such that D2 = (D1 \ {u}) ∪ {v}. In this paper, we present the γ-paired dominating graphs of cycles.
Źródło:
Opuscula Mathematica; 2022, 42, 1; 31-54
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Weakly convex and convex domination numbers
Autorzy:
Lemańska, M.
Powiązania:
https://bibliotekanauki.pl/articles/2050775.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating set
connected domination number
distance
isometric set
convex set
Opis:
Two new domination parameters for a connected graph G: the weakly convex domination number of G and the convex domination number of G are introduced. Relations between these parameters and the other domination parameters are derived. In particular, we study for which cubic graphs the convex domination number equals the connected domination number.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 181-188
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Triangle-free planar graphs with minimum degree 3 have radius at least 3
Autorzy:
Kim, Seog-Jim
West, Douglas
Powiązania:
https://bibliotekanauki.pl/articles/743089.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
radius
minimum degree
triangle-free
dominating set
Opis:
We prove that every triangle-free planar graph with minimum degree 3 has radius at least 3; equivalently, no vertex neighborhood is a dominating set.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 563-566
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Trees whose 2-domination subdivision number is 2
Autorzy:
Atapour, M.
Sheikholeslami, S. M.
Khodkar, A.
Powiązania:
https://bibliotekanauki.pl/articles/254847.pdf
Data publikacji:
2012
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
2-dominating set
2-domination number
2-domination subdivision numbe
Opis:
A set S of vertices in a graph G = (V,E) is a 2-dominating set if every vertex of V \ S is adjacent to at least two vertices of S. The 2-domination number of a graph G, denoted by γ2(G), is the minimum size of a 2-dominating set of G. The 2-domination subdivision number sdγ2 (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 2-domination number. The authors have recently proved that for any tree T of order at least 3, 1 ≤ sdγ2 (T ) ≤ 2. In this paper we provide a constructive characterization of the trees whose 2-domination subdivision number is 2.
Źródło:
Opuscula Mathematica; 2012, 32, 3; 423-437
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Quest for A Characterization of Hom-Properties of Finite Character
Autorzy:
Broere, Izak
Matsoha, Moroli D.V.
Heidema, Johannes
Powiązania:
https://bibliotekanauki.pl/articles/31340894.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
(countable) graph
homomorphism (of graphs)
property of graphs
hom-property
(finitely-)induced-hereditary property
finitely determined property
(weakly) finite character
axiomatizable property
compactness theorems
core
connectedness
chromatic number
clique number
independence number
dominating set
Opis:
A graph property is a set of (countable) graphs. A homomorphism from a graph \( G \) to a graph \( H \) is an edge-preserving map from the vertex set of \( G \) into the vertex set of \( H \); if such a map exists, we write \( G \rightarrow H \). Given any graph \( H \), the hom-property \( \rightarrow H \) is the set of \( H \)-colourable graphs, i.e., the set of all graphs \( G \) satisfying \( G \rightarrow H \). A graph property \( mathcal{P} \) is of finite character if, whenever we have that \( F \in \mathcal{P} \) for every finite induced subgraph \( F \) of a graph \( G \), then we have that \( G \in \mathcal{P} \) too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on \( H \) for \( \rightarrow H \) to be of finite character. A notable (but known) sufficient condition is that \( H \) is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those \( H \) for which \( \rightarrow H \) is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 479-500
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The domination number of $K_n^3$
Autorzy:
Georges, John
Lin, Jianwei
Mauro, David
Powiązania:
https://bibliotekanauki.pl/articles/30148694.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Cartesian product
dominating set
domination number
Opis:
Let $K_n^3$ denote the Cartesian product $K_n□K_n□K_n$, where $K_n$ is the complete graph on $n$ vertices. We show that the domination number of $K_n^3$ is $⌈\frac{n^2}{2}⌉$.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 629-632
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The Compared Costs of Domination Location-Domination and Identification
Autorzy:
Hudry, Olivier
Lobstein, Antoine
Powiązania:
https://bibliotekanauki.pl/articles/32083840.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph theory
dominating set
locating-dominating code
identifying code
twin-free graph
Opis:
Let G = (V, E) be a finite graph and r ≥ 1 be an integer. For v ∈ V, let Br(v) = {x ∈ V : d(v, x) ≤ r} be the ball of radius r centered at v. A set C ⊆ V is an r-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅; it is an r-locating-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct non-codewords x ∈ V \ C, y ∈ V \ C, we have Br(x) ∩ C ≠ Br(y) ∩ C; it is an r-identifying code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct vertices x ∈ V, y ∈ V, we have Br(x) ∩ C ≠ Br(y) ∩ C. We denote by γr(G) (respectively, ldr(G) and idr(G)) the smallest possible cardinality of an r-dominating code (respectively, an r-locating-dominating code and an r-identifying code). We study how small and how large the three differences idr(G)−ldr(G), idr(G)−γr(G) and ldr(G) − γr(G) can be.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 127-147
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning trees with many or few colors in edge-colored graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
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ł:
Optimal Locating-Total Dominating Sets in Strips of Height 3
Autorzy:
Junnila, Ville
Powiązania:
https://bibliotekanauki.pl/articles/31339416.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
locating-total dominating set
domination
square grid
strip
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 447-462
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Rainbow Vertex-Connection
Autorzy:
Li, Xueliang
Shi, Yongtang
Powiązania:
https://bibliotekanauki.pl/articles/30146636.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
rainbow vertex-connection
vertex coloring
minimum degree
2-step dominating set
Opis:
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It was proved that if $G$ is a graph of order $n$ with minimum degree $ \delta $, then $ rvc(G) < 11n//\delta$. In this paper, we show that $rvc(G) \le 3n//(δ+1)+5$ for $ \delta \ge \sqrt{n-1} -1 $ and $ n \le 290 $, while $ rvc(G) \le 4n//(δ + 1) + 5 $ for $ 16 \le \delta \le \sqrt{n-1}-2 $ and $ rvc(G) \le 4n//(\delta + 1) + C(\delta) $ for $6 \le \delta \le 15$, where $ C(\delta) = e^\frac{ 3 \log (\delta^3 + 2 \delta^2 +3)-3(\log 3 - 1)}{\delta - 3} - 2$. We also prove that $ rvc(G) \le 3n//4 − 2 $ for $ \delta = 3$, $ rvc(G) \le 3n//5 − 8//5$ for $\delta = 4$ and $rvc(G) \le n//2 − 2$ for $\delta = 5$. Moreover, an example constructed by Caro et al. shows that when $ \delta \ge \sqrt{n-1} - 1 $ and $ \delta = 3, 4, 5 $, our bounds are seen to be tight up to additive constants.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 307-313
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On non-z(mod k) dominating sets
Autorzy:
Caro, Yair
Jacobson, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743399.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating set
tree
unicyclic graph
Opis:
For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 189-199
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ł:
On Minimal Geodetic Domination in Graphs
Autorzy:
Nuenay, Hearty M.
Jamil, Ferdinand P.
Powiązania:
https://bibliotekanauki.pl/articles/31339437.pdf
Data publikacji:
2015-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
minimal geodetic dominating set
upper geodetic domination number
Opis:
Let $G$ be a connected graph. For two vertices $u$ and $v$ in $G$, a $u$-$v$ geodesic is any shortest path joining $u$ and $v$. The closed geodetic interval $ I_G[u, v] $ consists of all vertices of $G$ lying on any $u$-$v$ geodesic. For $ S \subseteq V (G) $, $S$ is a geodetic set in $G$ if \( \bigcup_{u,v \in S} I_G [u, v] = V (G) \). Vertices $u$ and $v$ of $G$ are neighbors if $u$ and $v$ are adjacent. The closed neighborhood $ N_G[v]$ of vertex $v$ consists of $v$ and all neighbors of $v$. For $S \subseteq V (G)$, $S$ is a dominating set in $G$ if \( \bigcup_{u \in S} N_G[u] = V (G) \). A geodetic dominating set in $G$ is any geodetic set in $G$ which is at the same time a dominating set in $G$. A geodetic dominating set in $G$ is a minimal geodetic dominating set if it does not have a proper subset which is itself a geodetic dominating set in $G$. The maximum cardinality of a minimal geodetic dominating set in $G$ is the upper geodetic domination number of $G$. This paper initiates the study of minimal geodetic dominating sets and upper geodetic domination numbers of connected graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 403-418
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Mf-Edge Colorings of Graphs
Autorzy:
Ivančo, Jaroslav
Onderko, Alfréd
Powiązania:
https://bibliotekanauki.pl/articles/32222570.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge coloring
anti-Ramsey number
dominating set
Opis:
An edge coloring φ of a graph G is called an Mf-edge coloring if |φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let Kf (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on Kf(G), present some graphs achieving the bounds and determine exact values of Kf(G) for some special classes of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1075-1088
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