Graphs with equal domination and 2-distance domination numbers

Joanna Raczek

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 375-385
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Joanna Raczek. "Graphs with equal domination and 2-distance domination numbers." Discussiones Mathematicae Graph Theory 31.2 (2011): 375-385. <http://eudml.org/doc/270826>.

@article{JoannaRaczek2011,
abstract = {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.},
author = {Joanna Raczek},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; trees; unicyclic graphs; distance domination number},
language = {eng},
number = {2},
pages = {375-385},
title = {Graphs with equal domination and 2-distance domination numbers},
url = {http://eudml.org/doc/270826},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Joanna Raczek
TI - Graphs with equal domination and 2-distance domination numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 375
EP - 385
AB - 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.
LA - eng
KW - domination number; trees; unicyclic graphs; distance domination number
UR - http://eudml.org/doc/270826
ER -

References

top
  1. [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). Zbl0344.05143
  2. [2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., 1998). Zbl0890.05002

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.