{"entities":{"Q992526":{"pageid":994374,"ns":120,"title":"Item:Q992526","lastrevid":65902665,"modified":"2026-04-12T06:09:25Z","type":"item","id":"Q992526","labels":{"en":{"language":"en","value":"Lights Out on finite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5781522"}},"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":"Q992526$D02A03AE-28E1-4C2F-8F1D-6A330D534895","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9adddf8b06deff4936389ac994953a4aeb90937f","datavalue":{"value":{"text":"Lights Out on finite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q992526$86B6EEDE-4AC3-4462-A317-54839AE15FAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf42fdaf930dce08d6d9137d26e64db5dad70390","datavalue":{"value":"1216.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$837A6FCF-93B1-4239-867A-DBDD2D03AD07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7b0acbbf035772c6b47976ae76e45aa061357341","datavalue":{"value":{"entity-type":"item","numeric-id":643185,"id":"Q643185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$95DBAC80-E9B8-4347-B1B2-407A77E1486D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f14f062e61469e2045aca8f66578f4714086511a","datavalue":{"value":{"entity-type":"item","numeric-id":992522,"id":"Q992522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$94E134CC-D3AB-49F7-ABE5-D5B6BF908C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fbd4e2236500fa5e3caf7b3c71fe40b3a6dae78","datavalue":{"value":{"entity-type":"item","numeric-id":992523,"id":"Q992523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$4D454B6E-E8DC-4168-A1B9-2E89DEE4A2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f26f3f048b1ca4ff9f89b48d363b8533c2aa8e2b","datavalue":{"value":{"entity-type":"item","numeric-id":444591,"id":"Q444591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$2AB72E4C-D1C0-4E46-8652-E008873E5549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e52e5c38be41e43743ac4b14730de36df902b8a","datavalue":{"value":{"entity-type":"item","numeric-id":1336688,"id":"Q1336688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$B5974A90-18C4-49B6-9C31-5F10713B5F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a846ba0cc87a453dbafe4447e7eaaf25a1e70b36","datavalue":{"value":{"entity-type":"item","numeric-id":1582238,"id":"Q1582238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$F4D24EE3-7ABC-41ED-9617-DA2E40A781DB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"481b96cb69972967979d166e912be39b92b70bcf","datavalue":{"value":{"entity-type":"item","numeric-id":258627,"id":"Q258627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$01647B89-92A2-4656-B8B8-98AE814122DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"587033a7b79934869c6b3f190356842a9070da4f","datavalue":{"value":{"time":"+2010-09-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":"Q992526$4A539FE8-9EFB-452B-AF60-741944AF60DF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23c51413690a5b1c7d11b8078ada2778cfff4605","datavalue":{"value":"A popular game on graphs, known as ``Lights Out!'', starts with an assignment of 0 or 1 to each vertex of a finite graph \\(G\\). A move consists of choosing a vertex and then adding \\(1 \\pmod 2\\) to the value of that vertex as well as to those of its neighbors. The object of the game is to find a sequence of moves that results in labeling all vertices of the graph 0. When this is possible, the initial labeling is said to be winnable. The existence of such a sequence of moves is related to the existence of an all-parity dominating set [see \\textit{A. T. Amin} and \\textit{P. J. Slater}, J. Comb. Math. Comb. Comput. 20, 53--63 (1996; Zbl 0845.05029)].    This game was generalized by A. Giffen and D. Parker (2009 preprint) by allowing the labels to be any value in \\({\\mathbb{Z}}_k\\), where addition is now modulo \\(k\\). A graph \\(G\\) is said to be \\textit{always winnable} (AW) over \\({\\mathbb{Z}}_k\\) if every initial labeling of \\(G\\) is winnable.   This paper considers this more general game and investigates properties of AW graphs over \\({\\mathbb{Z}}_k\\). In particular, the authors characterize AW spider graphs (Theorem 3.4) and AW generalized theta graphs (Theorem 4.4). These results are obtained by first characterizing all winning labelings for sub-collections of these graphs. The authors also prove that a graph \\(G\\) is AW over \\({\\mathbb{Z}}_k\\) if and only if \\(G\\) is AW over \\({\\mathbb{Z}}_p\\) for every prime factor \\(p\\) of \\(k\\) (Proposition 2.2 and Corollary 2.3), and generalize the construction of Amin and Slater (1996) of AW trees over \\({\\mathbb{Z}}_2\\) to produce AW trees over \\({\\mathbb{Z}}_p\\), where \\(p\\) is prime (Theorem 5.3).","type":"string"},"datatype":"string"},"type":"statement","id":"Q992526$191D65FE-A7F6-4B73-97C8-EFA18852ABCD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"baf5bcec01fc8167c888f6cffa70cf94f591bf61","datavalue":{"value":{"entity-type":"item","numeric-id":226044,"id":"Q226044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q992526$4E696D13-15D7-4382-B23E-B2ACB67D13F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$7F6ABD92-DFF0-47C3-81DB-64C39408E097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$4ADD47EF-6D5E-49E4-9559-1E6C294BD6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$7C925DBC-2201-454E-A91F-86B9E7606C65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1935d2722fe7251a5070ea7e66e27e414aaa5c1","datavalue":{"value":"5781522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$D71DA96A-07AE-4E00-B54C-F5462490F1FF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62e7ccbac5cc8ca02ded8b5b1557d66fbaa2e2eb","datavalue":{"value":"Lights Out","type":"string"},"datatype":"string"},"type":"statement","id":"Q992526$DA10ADAE-C7A0-4581-9EC5-8265778F5ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e528de04afc9355ddf2366eeffd1814d9465b17a","datavalue":{"value":"parity domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q992526$3419B036-2E16-43E9-A5F3-948E16300912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39beec85546d2cb532c8cec770d1e24ee62a7505","datavalue":{"value":"always winnable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q992526$D896996F-A7BF-4B0F-9C03-05833019D0A0","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":"Q992526$7783DCAB-6A74-44D4-8556-D72C4BC50D86","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b050b4d4e40a32de14b9879c8114a60d49991734","datavalue":{"value":"https://doi.org/10.2140/involve.2010.3.17","type":"string"},"datatype":"url"},"type":"statement","id":"Q992526$B97AADDC-15C2-4B7B-BEB3-E5A5C96D7AC4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d9897de1b216952ef974593fa80a13181f983885","datavalue":{"value":"W2104541075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$64759C75-EEBE-4DDB-B4B0-BE0942CF415C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8962de6cabe5ab789e539c9f0809ca2cd1759d8d","datavalue":{"value":"10.2140/INVOLVE.2010.3.17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q992526$08762790-D33C-4043-A366-FCC39F734B11","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25b35b61d695cbae9833336738033f955c2e1338","datavalue":{"value":{"entity-type":"item","numeric-id":2848975,"id":"Q2848975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fd138734661583770638415f0226c04fb9df705","datavalue":{"value":{"amount":"+0.8658930659294128","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":"Q992526$F621F63B-D0E3-4BBE-A39B-F551D19A4777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3a507600979a6058ffa794b82611ada06f612a7","datavalue":{"value":{"entity-type":"item","numeric-id":2088176,"id":"Q2088176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f99efbbfc76d22db6e33587d3ed023919ece823","datavalue":{"value":{"amount":"+0.8550425171852112","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":"Q992526$CB1C98B1-D744-4245-84DF-9AF86E800128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c361a75abe795ce76deb91b33f03271cae6fe91e","datavalue":{"value":{"entity-type":"item","numeric-id":4568211,"id":"Q4568211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b471ec0eb78675fc29388b70baead97ab185b5a9","datavalue":{"value":{"amount":"+0.8505188822746277","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":"Q992526$114CD22A-BCBB-4993-B87E-DCF50858D4CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a982665abd2cc4497977bb1f3cd007da4c434efc","datavalue":{"value":{"entity-type":"item","numeric-id":2931489,"id":"Q2931489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15b0e13c14236128c7993c2a1221f751b78dd4d8","datavalue":{"value":{"amount":"+0.8487968444824219","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":"Q992526$6B8B883A-2D4F-4B7E-86F5-82A541A11C86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d623a2fa69d1c093764a1486a1b3dce362bbe43","datavalue":{"value":{"entity-type":"item","numeric-id":2238462,"id":"Q2238462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9721d12bf6cfcb31d50583ce4043cb80cedd1bc","datavalue":{"value":{"amount":"+0.8484033346176147","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":"Q992526$05070D78-F4D2-4E1B-AC86-422553F9E2C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lights Out on finite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lights_Out_on_finite_graphs"}}}}}