Efficient Domination in Grid Graphs

被引:0
作者
Hutson, Kevin R. [1 ]
Hedetniemi, Stephen T. [2 ]
机构
[1] Department of Mathematics, Furman University, Greenville, 29613, SC
[2] Emeritus of Computer Science, Clemson University, Clemson, 29634, SC
来源
Journal of Combinatorial Mathematics and Combinatorial Computing | 2024年 / 122卷
关键词
Efficient dominating sets; Grid graphs; Minimum vertex removal;
D O I
10.61091/jcmcc122-27
中图分类号
学科分类号
摘要
Let G = (V, E) be a graph. A subset S ⊆ V of vertices is an efficient dominating set if every vertex v ∈ V is adjacent to exactly one vertex in S, where a vertex u ∈ S is considered to be adjacent to itself. Efficient domination is highly desirable in many real world applications, and yet, in general, graphs are often not efficient. It is of value, therefore, to determine optimum ways in which inefficient graphs can be changed in order to make them efficient. It is well known, for example, that almost no m × n grid graphs have efficient dominating sets. In this paper we consider the minimum number of vertices which can be removed from an m × n grid graph so that the remaining graph has an efficient dominating set. © 2024 the Author(s), licensee Combinatorial Press.
引用
收藏
页码:325 / 342
页数:17
相关论文
共 12 条
[1]  
Haynes T. W., Hedetniemi S. T., Slater P. J., Fundamentals of Domination in Graphs, (1998)
[2]  
Haynes T. W., Hedetniemi S. T., Slater P. J., Domination in Graphs: Advanced Topics, (1998)
[3]  
Haynes T. W., Henning M. A., Hedetniemi S. T., Domination in Graphs: Core Concepts, (2023)
[4]  
Alanko S., Crevals S., Insopoussu A., Ostergard P., Petterson V., Computing the domination number of grid graphs, Electronic Journal of Combinatorics, 18, 1, (2011)
[5]  
Chang T. Y., Clark W. E., The domination numbers of the 5 × n and 6 × n grid graphs, Journal of Graph Theory, 17, pp. 81-108, (1993)
[6]  
Chang T. Y., Clark W. E., Hare E. O., Dominations of complete grid graphs I, Ars Combinatoria, 38, pp. 97-112, (1994)
[7]  
Goncalves D., Pinlou A., Rao M., Thomasse S., The domination number of grids, SIAM Journal on Discrete Mathematics, 25, 3, pp. 1443-1453, (2011)
[8]  
Jacobson M. S., Kinch L. F., On the domination number of products of a graph, I, Ars Combinatoria, 10, pp. 33-44, (1983)
[9]  
Spalding A., A Min-plus Algebra Scheme for Computing Domination Numbers, (2001)
[10]  
Cockayne E. J., Hare E. O., Hedetniemi S. T., Wimer T. V., Bounds for the domination number of grid graphs, Congressus Numerantium, 47, pp. 217-228, (1985)