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: 4

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

Wyniki wyszukiwania

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

Secure domination and secure total domination in graphs

100%
Klostermeyer W., Mynhardt C.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 2
267-284
EN
A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-{x}) ∪ {u}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_{st}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{st}(G) ≤ γ_s(G)$. We also show that $γ_{st}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Analogues of cliques for oriented coloring

100%
Klostermeyer W., MacGillivray G.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
373-387
EN
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Odd and residue domination numbers of a graph

81%
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Connected odd dominating sets in graphs

81%
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.
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ć.