{"entities":{"Q2278125":{"pageid":2288868,"ns":120,"title":"Item:Q2278125","lastrevid":73018707,"modified":"2026-04-14T09:25:37Z","type":"item","id":"Q2278125","labels":{"en":{"language":"en","value":"Domination of the rectangular queen's graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7141295"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$AA4D5E79-C382-453F-A3E6-B91C126963DD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a1c655b306be9182f006a8c6af17bbb59050dde","datavalue":{"value":{"text":"Domination of the rectangular queen's graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2278125$523392F2-FCCD-4667-B064-C159CEC7B449","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e3381df811c93462a8c3b400a4e80e0bcca0ae90","datavalue":{"value":"1428.05228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2278125$B92DA81A-AFAE-4F5C-A1E3-6CAAF8392498","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"328ac61ab0cf1b2c00c428f5425ed3c1dc79e012","datavalue":{"value":{"entity-type":"item","numeric-id":302133,"id":"Q302133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$22CEC1C7-DFCD-40D7-9D57-AD5F7B13AD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"90865049f49233efed25204fb687085a632c35bb","datavalue":{"value":{"entity-type":"item","numeric-id":2278123,"id":"Q2278123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$CDD46E3A-B5DE-4BE7-B01C-9412D73C24EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1f30964cd0e58c28831ed8d2c0ee6b637b7dc8d","datavalue":{"value":{"entity-type":"item","numeric-id":2278124,"id":"Q2278124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$E79629B7-FABB-4DB7-AB2C-FFA11ED4F8CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d81c12937acbebbe6a1bf0976d9a46ca65b588e2","datavalue":{"value":{"entity-type":"item","numeric-id":200798,"id":"Q200798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$A3526110-211E-4818-ABCA-B3B3A8CCD863","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$04C4E2C7-CB4A-4014-A042-D05675651B1F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"952b5972e426ace2c3233f4c0cbc7ddf83bf0a55","datavalue":{"value":{"time":"+2019-12-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2278125$31219664-642F-4AA1-BFD1-6332847E8D76","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74e382e39ed7eb26dfd3aa156950ffdcce59434d","datavalue":{"value":"https://arxiv.org/abs/1606.02060","type":"string"},"datatype":"url"},"type":"statement","id":"Q2278125$E20B9020-C8FE-463C-971C-0C590D902771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"8180e224f5b6c7fa854a1e191ab8f500141f1298","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p45","type":"string"},"datatype":"url"},"type":"statement","id":"Q2278125$AB4546F0-CA3C-43D2-ACF2-B6A543E35D75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc5cf402bb963e5cd870e1d60699ef6d8487420f","datavalue":{"value":"Summary: The queens graph \\(Q_{m \\times n}\\) has the squares of the \\(m \\times n\\) chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal of the board. A set \\(D\\) of squares of \\(Q_{m \\times n}\\) is a dominating set for \\(Q_{m \\times n}\\) if every square of \\(Q_{m \\times n}\\) is either in \\(D\\) or adjacent to a square in \\(D\\). The minimum size of a dominating set of \\(Q_{m \\times n}\\) is the domination number, denoted by \\(\\gamma(Q_{m \\times n})\\).  Values of \\(\\gamma(Q_{m \\times n})\\), \\(4 \\leq m \\leq n \\leq 18\\), are given here, in each case with a file of minimum dominating sets (often all of them, up to symmetry) in an online appendix.  In these ranges for \\(m\\) and \\(n\\), monotonicity fails once: \\( \\gamma(Q_{8\\times 11}) = 6 > 5 = \\gamma(Q_{9 \\times 11}) = \\gamma(Q_{10 \\times 11}) = \\gamma(Q_{11 \\times 11})\\).  Let \\(g(m)\\) (respectively \\(g^\\ast(m)\\)) be the largest integer such that \\(m\\) queens suffice to dominate the \\((m+1) \\times g(m)\\) board (respectively, to dominate the \\((m+1) \\times g^\\ast(m)\\) board with no two queens in a row).  Starting from the elementary bound \\(g(m) \\leq 3m\\), domination when the board is far from square is investigated. It is shown (Theorem 2) that \\(g(m) = 3m\\) can only occur when \\(m \\equiv 0, 1, 2, 3\\), or \\(4 \\pmod 9\\), with an online appendix showing that this does occur for \\(m \\leq 40, m \\neq 3\\). Also (Theorem 4), if \\(m \\equiv 5, 6\\), or \\(7 \\pmod 9\\) then \\(g^\\ast(m) \\leq 3m-2\\), and if \\(m \\equiv 8 \\pmod 9\\) then \\(g^\\ast(m) \\leq 3m-4\\). It is shown that equality holds in these bounds for \\(m \\leq 40 \\).  Lower bounds on \\(\\gamma(Q_{m \\times n})\\) are given. In particular, if \\(m \\leq n\\) then \\(\\gamma(Q_{m \\times n}) \\geq \\min \\{ m,\\lceil (m+n-2)/4 \\rceil \\}\\).  Two types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of \\(\\gamma(Q_{m \\times n})\\) in several cases.  Three questions are posed: whether monotonicity of \\(\\gamma(Q_{m \\times n})\\) holds (other than from \\((m, n) = (8, 11)\\) to \\((9, 11))\\), whether \\(\\gamma(Q_{m \\times n}) = (m+n-2)/4\\) occurs with \\(m \\leq n < 3m+2\\) (other than for \\((m, n) = (3, 3)\\) and \\((11, 11))\\), and whether the lower bound given above can be improved.  A set of squares is independent if no two of its squares are adjacent. The minimum size of an independent dominating set of \\(Q_{m \\times n}\\) is the independent domination number, denoted by \\(i(Q_{m \\times n})\\). Values of \\(i(Q_{m \\times n})\\), \\(4 \\leq m \\leq n \\leq 18\\) are given here, in each case with some minimum dominating sets. In these ranges for \\(m\\) and \\(n\\), monotonicity fails twice: \\(i(Q_{8\\times 11}) = 6 > 5 = i(Q_{9 \\times 11}) = i(Q_{10 \\times 11}) = i(Q_{11 \\times 11})\\), and \\(i(Q_{11 \\times 18}) = 9 > 8 = i(Q_{12\\times 18})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2278125$EE49BC2A-9BEE-46FB-B1A1-335F744641AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2278125$B13F90E4-C0DB-44BC-A1F5-799DFB8605F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2278125$49E613CE-32A2-431E-99F9-2C1E484F25CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c108fc78e7f1c93fcdcefe1265d4ea7b49d1ea2","datavalue":{"value":"7141295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2278125$F3D80EFE-5B31-4640-A8EB-ECBF138B8D00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0d49d6d1c212943beca6feec904f51406efedfd","datavalue":{"value":"\\(m\\) queens problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2278125$61D8FEFC-3DF7-45A9-8FD3-7A4D2543C564","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$FA837154-C4C5-407D-9AC7-ADA7F9D55D84","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a63cd4e96558c1b46312c4626e1dee97acf3b915","datavalue":{"value":{"entity-type":"item","numeric-id":4500610,"id":"Q4500610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$69E857AF-C648-43DE-BDE3-60385994C1B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"091caff7a7ff7dce8f11c015d37114da52e8a852","datavalue":{"value":{"entity-type":"item","numeric-id":4309111,"id":"Q4309111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$ECDA8CCB-7CC9-4097-9CE6-1EDCC1496847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a86926a4c615982286a32357c9d5918a96fe673b","datavalue":{"value":{"entity-type":"item","numeric-id":5236471,"id":"Q5236471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$853736F3-60B2-4C22-943F-50396821E7C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de79b1f3d6590cab06a17d3fbe88acdf6787fb35","datavalue":{"value":{"entity-type":"item","numeric-id":1174120,"id":"Q1174120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$BF444403-EEAB-456D-AB1D-4BEA4BA4AAEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a459cd3c518f53d9022948083e39a5322091217","datavalue":{"value":{"entity-type":"item","numeric-id":3139865,"id":"Q3139865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$8FCF5D59-56BF-4709-8DF6-080AE06FF820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5709b92f151e11e33b0f33fa1e24a68df1d56dd4","datavalue":{"value":{"entity-type":"item","numeric-id":968146,"id":"Q968146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$57A47C34-32C4-4E24-BF11-420935CA8E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d732d4980c3fbacaacf091e5eb1fdf58f3b2219","datavalue":{"value":{"entity-type":"item","numeric-id":5294944,"id":"Q5294944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$67303C34-91C3-4872-9811-BFA54FBB7CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea526f433c2ba07124e2f10f76ba15541ea2703f","datavalue":{"value":{"entity-type":"item","numeric-id":4349621,"id":"Q4349621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$B9BAFA38-52F2-4D2B-96ED-FC01CEA091FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849c2c907b884c9c6bbf31be85ca7b9fca09f814","datavalue":{"value":{"entity-type":"item","numeric-id":2712528,"id":"Q2712528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$63680D1B-0D38-4A51-9E40-5101CE80F833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1842a56b0a7f7d053604d73f0145d4a79cc0b84","datavalue":{"value":{"entity-type":"item","numeric-id":5942492,"id":"Q5942492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$2256DEF6-A292-4003-9B6B-196984D6F642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde75aeda17a03a1ad4eb5214c55464a8c19f681","datavalue":{"value":{"entity-type":"item","numeric-id":1101453,"id":"Q1101453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$B2DB8757-884D-41F0-85A8-EAF7A8192E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3e90ddf41c1d7b432c65d3c89d25bcb7b6a4c5a","datavalue":{"value":{"entity-type":"item","numeric-id":4821596,"id":"Q4821596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$EF0FE25F-5B3C-418A-9D6A-0EF31041AA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db4017fb9c1d352a4c895c9543b3bbed5cfbc549","datavalue":{"value":{"entity-type":"item","numeric-id":4871084,"id":"Q4871084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$F6C7B278-CBE1-43AF-B58F-511D15F7677B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb7cf00d193391a6da881e871f78c84297a9ec10","datavalue":{"value":{"entity-type":"item","numeric-id":4798534,"id":"Q4798534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$3AA5297B-3F7B-495C-8FBB-6E11075EB806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a39a8eb7915c40253f0a5e87e4dd3701fd894da","datavalue":{"value":{"entity-type":"item","numeric-id":5957757,"id":"Q5957757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$D11F793F-3590-4D92-ABC0-045723DCC212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be461cf623b5e7e53989debd9a29b3c9cd9becec","datavalue":{"value":{"entity-type":"item","numeric-id":5378297,"id":"Q5378297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2278125$1604929A-2BF4-4206-8624-DD843865A2E3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"415be65ca1955ad54af8f7f4bcd7dd7c68a5014c","datavalue":{"value":"bafkreibs3pclxjld5zes6hhikw5uuxcrn26gcvxh5cmv36syjc5hqoq73u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2278125$CF18E937-E1D1-4C22-B4B9-9774FE747125","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c05a1e909801c171d399648d60bd0f9436c5884","datavalue":{"value":{"entity-type":"item","numeric-id":5942492,"id":"Q5942492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc6da7118d9a7197f512cd2393dde26169bddeed","datavalue":{"value":{"amount":"+0.936896562576294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2278125$B642B543-3311-4E77-87EE-E61523A16C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c5fefa547e078382645da5ac6f5adbc2bf4cba7","datavalue":{"value":{"entity-type":"item","numeric-id":1356524,"id":"Q1356524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0ffe01652670a719a49df85b2f357bee897fdb","datavalue":{"value":{"amount":"+0.9357882738113404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2278125$E9BE3A26-0A3D-4C72-B4C2-3C0C32E995CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2938479d44eb665948685e2b8d1074f274560e5c","datavalue":{"value":{"entity-type":"item","numeric-id":2152788,"id":"Q2152788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90fa7dcc5d963a587f6e41d17f929b6da4b852e8","datavalue":{"value":{"amount":"+0.914913296699524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2278125$2EA37CFF-D742-4792-A966-3EC46B7A7F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6685bf10f5656170805418dfe7c36cbe40e2a45b","datavalue":{"value":{"entity-type":"item","numeric-id":4871084,"id":"Q4871084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3981f094804f642a66169c2635ba7da3adf06da1","datavalue":{"value":{"amount":"+0.9138656258583068","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2278125$AF6A8323-B348-4365-8F61-9CC8D189D994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e63a1c7be4833d61e78673d1352a4a04c6d10a4","datavalue":{"value":{"entity-type":"item","numeric-id":4500610,"id":"Q4500610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed71b4f420115078d062230c47f7381f81b1cb1","datavalue":{"value":{"amount":"+0.9137686491012572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2278125$EDA90676-0150-4C0A-B45A-061C7F0561D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Domination of the rectangular queen's graph","badges":[]}}}}}