Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Domination Subdivision Numbers

100%

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

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Haynes T.

1 Hedetniemi S.

1 Jacobs D.

1 Knisely J.

1 van der Merwe L.

1 2001

Wyniki wyszukiwania

Domination Subdivision Numbers