Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 17

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  dominating set
help Sortuj według:

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

A characterization of roman trees

100%
Henning M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
325-334
EN
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.
2
Content available remote

Gamma Graphs Of Some Special Classes Of Trees

100%
Bień A.
Annales Mathematicae Silesianae
|
2015
|
tom 29
|
nr 1
25-34
EN
A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs γ.T of trees with diameter not greater than five will be presented. It will be shown that hypercubes Qk are among γ.T graphs. In the third section γ.T graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented, in response to an open question, published by Fricke et al., if diam(T (γ)) = O(n)?
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Connected odd dominating sets in graphs

100%
Caro Y., Klostermeyer W., Yuster R.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
225-239
EN
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Odd and residue domination numbers of a graph

80%
Caro Y., Klostermeyer W., Goldwasser J.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
119-136
EN
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.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On non-z(mod k) dominating sets

80%
Caro Y., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
189-199
EN
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.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Mean value for the matching and dominating polynomial

80%
Arocha J., Llano B.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 1
57-69
EN
The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination in partitioned graphs

80%
Tuza Z., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
199-210
EN
Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
8
Content available remote

Domination, Eternal Domination, and Clique Covering

80%
Klostermeyer W. F., Mynhardt C. M.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 2
283-300
EN
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.
9
Content available remote

The Domination Number of K3n

80%
Georges J., Lin J., Mauro D.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
629-632
EN
Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]
10
Content available remote

Eternal Domination: Criticality and Reachability

80%
Klostermeyer W. F., MacGillivray G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
63-77
EN
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.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Highly connected counterexamples to a conjecture on α-domination

80%
Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
435-440
EN
An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Independent transversal domination in graphs

80%
Hamid I.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 1
5-17
EN
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.
13
Content available remote

A Note on the Locating-Total Domination in Graphs

71%
Miller M., Rajan R. S., Jayagopal R., Rajasingh I., Manuel P.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
745-754
EN
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.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Triangle-free planar graphs with minimum degree 3 have radius at least 3

71%
Kim S.-J., West D.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
563-566
EN
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.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dominating bipartite subgraphs in graphs

71%
Bacsó G., Michalak D., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
85-94
EN
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graph domination in distance two

71%
Bacsó G., Tálos A., Tuza Z.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
121-128
EN
Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class 𝓓 of graphs, Domₖ 𝓓 is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ 𝓓 which is also connected. In our notation, Dom𝓓 coincides with Dom₁𝓓. In this paper we prove that $Dom Dom 𝓓_u = Dom₂ 𝓓_u$ holds for $𝓓_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, 𝓓₂ = {K₁} and 𝓓₃ = {all complete graphs}.) Some negative examples are also given.
17
Content available remote

The Quest for A Characterization of Hom-Properties of Finite Character

41%
Broere I., Matsoha M. D. V., Heidema J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
479-500
EN
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 → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ 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 →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 →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.
first rewind previous Strona / 1 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ć.