No Detail Found!

Improved bounds on the domatic numbers of queens graphs

Author(s)
Juho Lauri Helsinki, Finland
Abstract
The queens graph Qn, for any positive integer n, has the n2 squares of the n × n chessboard as its vertices with two vertices adjacent if and only if they are on the same row, column, or diagonal of the board. Recently, Hedetniemi et al. [Congr. Numer. 235 (2024) 5-21] determined exact values or provided bounds for the domatic, idomatic, and total domatic number of Qn for n up to 9. For an undirected graph G, these numbers are denoted by dom(G), idom(G), and tdom(G), respectively, and defined as the maximum order k for which a partition {V 1, V2, . . . , Vk} of V (G) into (dominating, independent dominating, total dominating) sets exists. In this paper, using a computational approach based on SAT solvers, some of their open questions are settled precisely, and improvements upon their bounds are obtained. In particular, for the domatic number, it is shown that dom(Q7) = 11, dom(Q9) = 13, dom(Q10) = 16, dom(Q11) ? {18, 19, 20}, and dom(Q12) ? {20, 21}. For the idomatic number, it is shown that idom(Q9) = 14, idom(Q10) ? {15, 16}, idom(Q11) = 17, and idom(Q12) ? {18, 19, 20}. Finally, for the total domatic number, it is established that tdom(Q9) = 14, tdom(Q10) ? {15, 16}, tdom(Q11) ? {16, 17}, and tdom(Q12) ? {18, 19, 20}.
Publication Details
Page(s) 94-99
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
Graphs, computational combinatorics, domatic number, domination
References
Balint A.,A. A.,Strichman A. .2010 .Fro¨hlich, Improving stochastic local search for SAT with a new probability distribution. SAT 2010: 13th International Conference on Theory and Applications of Satisfiability Testing, 15 8 13 16 5 2 14 8 9 6 5 0 3 4(a) : 10-15.
Biere A.,Faller T.,Fazekas K.,Fleury M.,Froleyks N.,Pollitt F.,Gurfinkel F. .2024 .. CAV, 2 : 133-152.
Biere A.,Heule M.,H. van Maaren M. .2009 .. Handbook of Satisfiability, : .
Bowtell C.,Keevash P. .2021 .The n-queens problem. arXiv:2109.08083, : .
Cockayne E.,Hedetniemi S. .1975 .Optimal domination in graphs. IEEE Trans. Circ. Syst, 22(11) : 855-857.
Hedetniemi J. T.,Hedetniemi K. D.,Hedetniemi S. M.,Hedetniemi S. T. .2024 .On the domatic numbers of queens graphs. Congr. Numer, 235 : 5-21.
Heggernes P.,Telle J. A. .1998 .Partitioning graphs into generalized dominating sets. Nord. J. Comput, 5(2) : 128-142.
Ignatiev A.,Morgado A.,Beyersdorf A.,C. M. Wintersteiger A. .2018 .PySAT: A Python toolkit for prototyping with SAT oracles. SAT 2018: 21st International Conference on Theory and Applications of Satisfiability Testing, : 428-437.
Ignatiev A.,Tan Z. L.,Karamanos C. .2024 .Towards universally accessible SAT technology. SAT 2024: 27th International Conference on Theory and Applications of Satisfiability Testing, 16 : 11-16.
Sinz C. .2005 .Towards an optimal CNF encoding of boolean cardinality constraints. CP 2005: 11th International Conference on Principles and Practice of Constraint Programming, : 827-831.
Vasquez M. .2004 .New results on the Queensn2 graph coloring problem. J. Heuristics, 10(4) : 407-413.
Vasquez M.,Habet D.,de M a D. .2004 .´ntaras. ECAI 2004: 16th European Conference on Artificial Intelligence, : 226-230.
Vasquez M.,Vimont Y.,Brankovic J.,Ryan W. F.,Smyth W. F. .2017 .On solving the queen graph coloring problem. IWOCA 2017: 28th International Workshop on Combinatorial Algorithms, : 244-251.
Zelinka B.,Hedetniemi S. T.,Slater S. T. .2017 .Domatic numbers of graphs and their variants: a survey. , : 351-378.
0

Citations

0

Downloads

24

Views