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

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

Trees with unique minimum total dominating sets

100%
Haynes T., Henning M.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
233-246
EN
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Global alliances and independence in trees

100%
Chellali M., Haynes T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
19-27
EN
A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination and independence subdivision numbers of graphs

81%
Haynes T., Hedetniemi S., Hedetniemi S.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
271-280
EN
The domination subdivision number $sd_γ(G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices in G. We then define the independence subdivision number $sd_β(G)$ to equal the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the independence number. We show that for any graph G of order n ≥ 2, either $G = K_{1,m}$ and $sd_β(G) = m$, or $1 ≤ sd_β(G) ≤ 2$. We also characterize the graphs G for which $sd_β(G) = 2$.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination edge critical graphs with maximum diameter

81%
van der Merwe L., Mynhardt C., Haynes T.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
187-205
EN
Denote the total domination number of a graph G by γₜ(G). A graph G is said to be total domination edge critical, or simply γₜ-critical, if γₜ(G+e) < γₜ(G) for each edge e ∈ E(G̅). For 3ₜ-critical graphs G, that is, γₜ-critical graphs with γₜ(G) = 3, the diameter of G is either 2 or 3. We characterise the 3ₜ-critical graphs G with diam G = 3.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds on the global offensive k-alliance number in graphs

81%
Chellali M., Haynes T., Randerath B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
597-613
EN
Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total domination subdivision numbers of graphs

81%
Haynes T., Henning M., Hopkins L.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
457-467
EN
A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families of graphs. Then we show that the total domination subdivision number of a graph can be arbitrarily large.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

k-independence stable graphs upon edge removal

81%
Chellali M., Haynes T., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
265-274
EN
Let k be a positive integer and G = (V(G),E(G)) a graph. A subset S of V(G) is a k-independent set of G if the subgraph induced by the vertices of S has maximum degree at most k-1. The maximum cardinality of a k-independent set of G is the k-independence number βₖ(G). A graph G is called β¯ₖ-stable if βₖ(G-e) = βₖ(G) for every edge e of E(G). First we give a necessary and sufficient condition for β¯ₖ-stable graphs. Then we establish four equivalent conditions for β¯ₖ-stable trees.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination Subdivision Numbers

62%
Haynes T., Hedetniemi S., Hedetniemi S., Jacobs D., Knisely J., van der Merwe L.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
239-253
EN
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $sd_γ(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 domination number. Arumugam conjectured that $1 ≤ sd_γ(G) ≤ 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that $sd_γ(G) ≤ γ(G)+1$ for any graph G without isolated vertices, and give constant upper bounds on $sd_γ(G)$ for several families of graphs.
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ć.