TREES WITH EQUAL PERFECT AND RESTRAINED DOMINATION NUMBERS
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A set D of vertices of a graph G is a perfect dominating set if every vertex in V \ D is adjacent to exactly one vertex in D. The perfect domination number of G, is the minimum cardinality of a perfect dominating set of G. A set D of verices is a restrained dominating set if every vertex in V \D is adjacent to a vertex in D and another vertex in V \D. The restrained domination number is the minimum cardinality of a restrained dominating set of G. We characterize all trees for which perfect domination and restrained domination numbers are equal.
Abstract
A set D of vertices of a graph G is a perfect dominating set if every vertex in V \ D is adjacent to exactly one vertex in D. The perfect domination number of G, is the minimum cardinality of a perfect dominating set of G. A set D of verices is a restrained dominating set if every vertex in V \D is adjacent to a vertex in D and another vertex in V \D. The restrained domination number is the minimum cardinality of a restrained dominating set of G. We characterize all trees for which perfect domination and restrained domination numbers are equal.
참고문헌 (9)
- H. Aram, "Domination subdivision numbers of trees", Discrete Math, 309, pp.622~628 (2009)
- P.Dankelmann, "Trees with equal domination and restrained domination numbers", Journal of Global Optimization, 34, pp.597~607 (2006)
- G. S. Domke, "Restrained domination in graphs", Discrete Math, 203, pp.61~69 (1999)
- T. W. Haynes, "Domination in Graphs: Advanced Topics" (1998), Marcel Dekker
- T. W. Haynes, "Fundamentals of Domination in Graphs" (1998), Marcel Dekker
- J. H. Hattingh, "Characterization of trees with equal domination parameters", Journal of Graph Theory, 34, pp.142~153 (2000)
- J.Raczek, "Trees with equal restrained domination and total restrained domination numbers", Discuss. Math. Graph Theory, 27, pp.83~91 (2007)
- B. Sharada, "Perfect domination excellent trees", Int. Journal of Mathematical Combinatorics, 2, pp.76~80 (2012)
- J. A. Telle, "Algorithms for vertex partitioning problems on partial k-trees", SIAM Journal of Discrete Math, 10, pp.529~550 (1997)