The domination numbers of cylindrical grid graphs

详细信息    查看全文

• 作者：Mrinal Nandi^a ; ^{mrinal.nandi1@gmail.com} ; Subrata Parui^b ; ^{subrata.parui@gmail.com} ; Avishek Adhikari^c ; ^{aamath@caluniv.ac.in}
• 关键词：Minimum dominating set ; Grid graph ; Cycle ; Path and Cartesian product of graphs
• 刊名：Applied Mathematics and Computation
• 出版年：2011
• 出版时间：15 January 2011
• 年：2011
• 卷：217
• 期：10
• 页码：4879-4889
• 全文大小：452 K

文摘

Let γ(P_m □ C_n) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P_m, the path of length m, m  2 and the graph C_n, the cycle of length n, n  3. In this paper, methods to find the domination numbers of graphs of the form P_m □ C_n with n  3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P₅ □ C_n, n  3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.