Construction for trees with unique minimum dominating sets. Issue 3 (3rd July 2018)

• Record Type: Journal Article
• Authors: Zhao, Weisheng; Wang, Fan; Zhang, Heping
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 3(2018)
• Page Start: 204
• Page End: 213
• Publication Date: 2018-07-03
• Subjects: Tree -- minimum dominating set -- universal vertex -- idle vertex -- alterable vertex; 05C05 -- 05C69; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1531930
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: A vertex v of a graph G is called universal if v belongs to every minimum dominating set of G, idle if v does not belong to any minimum dominating set of G, and alterable if v is neither universal nor idle. G. Gunther et al. gave a constructive characterization for trees with unique minimum dominating sets. Note that a tree has a unique minimum dominating set if and only if it has no alterable vertex. Based on this result, we characterize trees with unique minimum dominating sets via refining the construction of G. Gunther et al.