Graphs with equal domination and 2-distance domination numbers

• Autorzy: Joanna Raczek
• Języki publikacji: EN

Abstrakty

EN

Let G = (V,E) be a graph. The distance between two vertices u and v in a connected graph G is the length of the shortest (u-v) path in G. A set D ⊆ V(G) is a dominating set if every vertex of G is at distance at most 1 from an element of D. The domination number of G is the minimum cardinality of a dominating set of G. A set D ⊆ V(G) is a 2-distance dominating set if every vertex of G is at distance at most 2 from an element of D. The 2-distance domination number of G is the minimum cardinality of a 2-distance dominating set of G. We characterize all trees and all unicyclic graphs with equal domination and 2-distance domination numbers.

Słowa kluczowe

EN

domination number; trees; unicyclic graphs

Kategorie tematyczne

• 05C05: Trees
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 2
• Strony: 375-385

Daty

wydano

2011

otrzymano

2009-12-18

poprawiono

2010-06-15

zaakceptowano

2010-08-25

Twórcy

autor

Joanna Raczek

• Department of Applied Physics and Mathematics, Gdansk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] M. Borowiecki and M. Kuzak, On the k-stable and k-dominating sets of graphs, in: Graphs, Hypergraphs and Block Systems. Proc. Symp. Zielona Góra 1976, ed. by M. Borowiecki, Z. Skupień, L. Szamkołowicz, (Zielona Góra, 1976).
• [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998).

Identyfikatory

DOI

10.7151/dmgt.1552