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

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

Graphs with small additive stretch number

100%
Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
291-301
EN
The additive stretch number $s_{add}(G)$ of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with $s_{add}(G) ≤ k$ for some k ∈ N₀ = {0,1,2,...}. Furthermore, we derive characterizations of these classes for k = 1 and k = 2.
2
Content available remote

Remarks on Dynamic Monopolies with Given Average Thresholds

64%
Centeno C. C., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
133-140
EN
Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optimization 9 (2012) 77-83] and Zaker [Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math. 161 (2013) 2716-2723].
3
Content available remote

Relating 2-Rainbow Domination To Roman Domination

51%
Alvarado J. D., Dantas S., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 4
953-961
EN
For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer k, the recognition of the connected K4-free graphs G with yR(G) − yr2(G) = k is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs G such that yr2(H) = yR(H) for every induced subgraph H of G, and collect several properties of the graphs G with R(G) = 3/2yr2(G).
4
Content available remote

Hereditary Equality of Domination and Exponential Domination

51%
Henning M. A., Jäger S., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
275-285
EN
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.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partitioning a graph into a dominating set, a total dominating set, and something else

51%
Henning M., Löwenstein C., Rautenbach D.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 4
563-574
EN
A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some remarks on α-domination

51%
Dahme F., Rautenbach D., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
423-430
EN
Let α ∈ (0,1) and let $G = (V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D ⊆ V_G$ is called an α-dominating set of G, if $|N_G(u) ∩ D| ≥ αd_G(u)$ for all $u ∈ V_G∖D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On 𝓕-independence in graphs

51%
Göring F., Harant J., Rautenbach D., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
377-383
EN
Let 𝓕 be a set of graphs and for a graph G let $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in 𝓕 as a subgraph and which does not contain a graph in 𝓕 as an induced subgraph, respectively. Lower bounds on $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ are presented.
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ć.