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

Domination and independence subdivision numbers of graphs

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

γ-graphs of graphs

100%
Fricke G., Hedetniemi S., Hedetniemi S., Hutson K.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
517-531
EN
A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ-graph G(γ) = (V(γ), E(γ)) of G to be the graph whose vertices V(γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D₁ and D₂, are adjacent in E(γ) if there exists a vertex v ∈ D₁ and a vertex w ∈ D₂ such that v is adjacent to w and D₁ = D₂ - {w} ∪ {v}, or equivalently, D₂ = D₁ - {v} ∪ {w}. In this paper we initiate the study of γ-graphs of graphs.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination Subdivision Numbers

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

Offensive alliances in graphs

64%
Favaron O., Fricke G., Goddard W., Hedetniemi S., Hedetniemi S., Kristiansen P., Laskar R., Skaggs R.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
263-275
EN
A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.
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ć.