Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: connected domination

Sortuj według:

Ogranicz wyniki do:

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

Graphs without induced P₅ and C₅

100%

Bacsó G., Tuza Z.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 3

503-507

Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.

Graph domination in distance two

100%

Bacsó G., Tálos A., Tuza Z.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 1-2

121-128

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class 𝓓 of graphs, Domₖ 𝓓 is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ 𝓓 which is also connected. In our notation, Dom𝓓 coincides with Dom₁𝓓. In this paper we prove that $Dom Dom 𝓓_u = Dom₂ 𝓓_u$ holds for $𝓓_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, 𝓓₂ = {K₁} and 𝓓₃ = {all complete graphs}.) Some negative examples are also given.

Domination Parameters of a Graph and its Complement

86%

Desormeaux W. J., Haynes T. W., Henning M. A.

Discussiones Mathematicae Graph Theory

2017

tom 38

nr 1

203-215

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

2 Bacsó G.

2 Tuza Z.

1 Desormeaux W. J.

1 Haynes T. W.

1 Henning M. A.

1 Tálos A.

1 2018

1 2005

1 2004

Wyniki wyszukiwania

Graphs without induced P₅ and C₅

Graph domination in distance two

Domination Parameters of a Graph and its Complement