EFFICIENT AND PERFECT DOMINATION ON ARCHIMEDEAN LATTICES

domination;Archimedean lattice;Applied Mathematics & Statistics

Zhao, YunfanWierman, John C ;

Johns Hopkins University

关键词: domination;    Archimedean lattice;    Applied Mathematics & Statistics;   

Others  :  https://jscholarship.library.jhu.edu/bitstream/handle/1774.2/60171/ZHAO-THESIS-2018.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: JOHNS HOPKINS DSpace Repository

【 摘 要 】

An Archimedean lattice is an infinite graph constructed from a vertex-transitive tiling of the plane by regular polygons. A set of vertices S is said to dominate a graph G=(V,E) if every vertex in V is either in the set S or is adjacent to a vertex in set S. A dominating set is a perfect dominating set if every vertex not in the dominating set is dominated exactly once. The domination ratio is the minimum proportion of vertices in a dominating set. The perfect domination ratio is the minimum proportion of vertices in a perfect dominating set. Dominating sets are provided to establish upper bounds for the domination ratios of all the Archimedean lattices. A dominating set is an efficient dominating set if every vertex is dominated exactly once. We show that seven of the eleven Archimedean lattices are efficiently dominated, which easily determine their domination ratios and perfect domination ratios. We prove that the other four Archimedean lattices cannot be efficiently dominated. For the four Archimedean lattices that cannot be efficiently dominated, we have determined their exact perfect domination ratios. Integer programming bounds for domination ratios are provided. A perfect domination proportion is the proportion of vertices in a perfect dominating set that is not necessarily minimal. We study nonisomorphic perfect dominating sets and possible perfect domination proportions of Archimedean lattices.