{"entities":{"Q2519798":{"pageid":2530541,"ns":120,"title":"Item:Q2519798","lastrevid":73278486,"modified":"2026-04-14T15:15:14Z","type":"item","id":"Q2519798","labels":{"en":{"language":"en","value":"Lit-only sigma game on a line graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5498582"}},"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":"Q2519798$3BB1701D-C739-4F7A-BBDE-84E9547A5227","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"21b58fd3bcaafa77de40f6994bfdcfa4a09a0019","datavalue":{"value":{"text":"Lit-only sigma game on a line graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2519798$BC2359B4-92EB-43AD-8E88-491B96497A15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f0dcc5359bc49057cb815bd5432aca14d9414995","datavalue":{"value":"1166.91010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519798$EB31ED38-AC80-4135-8FE8-FF57D1C4CFEE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4da0ece172977e42c087f9921d285313bc8a74e","datavalue":{"value":{"entity-type":"item","numeric-id":233542,"id":"Q233542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$3C216AA7-DE38-42D3-84D6-AD2A71D75869","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$D682CEDF-D0CE-4D47-9019-A930243F678F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"51e6c39ac6ec91b8381a06fe1e16cf5aca0f2bdc","datavalue":{"value":{"time":"+2009-01-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2519798$2A07FB80-9691-4A6B-8D4B-7951C35ABA79","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81166e9f69c6690314d5a9f71dffde8d869f31ec","datavalue":{"value":"Let \\(\\Gamma \\) be a connected graph and \\(V(\\Gamma )\\) its vertex set. Denote by \\(\\mathbb{F}\\) the set of functions from \\(V(\\Gamma )\\) to the binary field \\(\\mathbb{F}_{2}\\). For any \\(x\\in \\mathbb{F}\\), a move of the lit-only sigma game on \\(\\Gamma \\) consists of choosing some vertex \\(v\\) with \\(x(v)=1\\) and changing the values of \\(x\\) at all those neighbors of \\(v\\). An orbit is a maximal subset of \\(\\mathbb{F}\\) satisfying the property that any two elements can reach each other by a series of moves. The minimum light number of \\(\\Gamma \\) is \\(\\max_{K}\\min_{x\\in K}\\#\\text{supp}(x)\\), where \\(K\\) runs through all orbits. It is shown that the minimum light number of the line graph of \\(\\Gamma \\) is equal to \\(\\max \\{b(\\Gamma ),\\rho (\\sigma ^{1}(\\Gamma ))\\}\\), where \\(b(\\Gamma )\\) is the isoperimetric number of \\(\\Gamma \\) and \\(\\rho (\\sigma ^{1}(\\Gamma ))\\) is the covering radius of the subspace of set of functions from \\(E(\\Gamma )\\) (the set of edges of \\(\\Gamma \\)) to the binary field \\(\\mathbb{F}_{2}\\) generated by the rows of the adjacency matrix of \\(L(\\Gamma )\\). The sizes of all orbits of the lit-only sigma game on \\(L(\\Gamma )\\) are also determined. It is also shown that when \\(\\Gamma \\) is a tree, the minimum light number of \\(L(\\Gamma )\\) is \\(b(\\Gamma )\\). Furthermore, it is shown that, if the tree has \\(n\\geq 3\\) vertices, the group formed by the moves of the lit-only sigma game on \\(L(\\Gamma )\\) is the symmetric group on \\(n \\) elements.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$072C1AE4-E819-4CDB-B989-AC7776757349","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b62273aea3375cefac54cd8688def5a3b6704b92","datavalue":{"value":"91A46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519798$84706852-EC6B-43DB-B25A-DF2A5C1BD78C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c6b0ee4a618fef850c246493afc291b60ea2d5b","datavalue":{"value":"5498582","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519798$B90E1B2D-563B-4E48-B25D-E0B83FDD7094","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bbea51f013c2133dd5e214f6e998f4b3decd3b9","datavalue":{"value":"lit-only sigma game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$5A80D1FD-9085-4839-94B7-03535D4F7A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$817CADBD-77EA-4A22-BDA3-4BF659D16672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d1cb0c92ec117e721722563d91e34f49c8d853c","datavalue":{"value":"orbit","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$9FD4158C-2AC2-47B8-9371-3BC88CDC867E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62c7b836dcd5a85b54e53ca8fa579f8e2d1022b2","datavalue":{"value":"minimum light number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$C0ED6004-49B8-4534-9D11-5E6AA97C9AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bfa7ad7cc229e2d9ec43c2e311ac196f27a13cb","datavalue":{"value":"isoperimetric number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$343FD298-4EF5-4AAD-9590-9670B92C8B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fae759507bb9563b997a3ae1e2c1987b9dc770fd","datavalue":{"value":"covering radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$4A6BC1FB-8542-4A30-95E1-112D7AB185CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$F8922521-EE16-430B-9252-992E26AE3D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38d830dae6f5ce906f6d20604a81e37d7574c069","datavalue":{"value":"symmetric group","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519798$AE137C24-AF34-4082-9D05-E8849CAF918C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$C2BE91CC-C41D-40E9-9E1A-89933380D322","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":"Q2519798$4212298F-D328-4FE6-86CE-D2ACACB74841","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c0708fda3900bdba7d4637de99de9be0ac930eb","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2008.02.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q2519798$729C1C57-0227-48B8-A02E-5FF9004010BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94f04a99d34ca00e77611793edaaf659a45565f4","datavalue":{"value":"W2121594428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519798$78CDB025-1184-4A3E-883C-37EAD7211A56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a5e21c79f3dd7fe76f3449d5fe1009f7827392a","datavalue":{"value":{"entity-type":"item","numeric-id":4326630,"id":"Q4326630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$5C8BD3EC-18E8-407B-9B8E-829468930E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7efc8f4f1201055801f815ed507db2bb97b5fbe9","datavalue":{"value":{"entity-type":"item","numeric-id":1011720,"id":"Q1011720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$E2C51040-80CF-42F9-8E52-2B4EFC8DEFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b97b7b371790c7a130cae541abb3a3d2037405ef","datavalue":{"value":{"entity-type":"item","numeric-id":1887574,"id":"Q1887574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$E01D51DF-75F4-493C-BCEA-F920A3C85061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1b7718e9dd6179a71b1f4dbb41b77c4ae3dd21c","datavalue":{"value":{"entity-type":"item","numeric-id":2498877,"id":"Q2498877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$EB4FE7E6-301F-4F94-AA1E-2B679FE84B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2854cda7e5988d324d2751b394a4a2ff4b92b03a","datavalue":{"value":{"entity-type":"item","numeric-id":4769056,"id":"Q4769056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$C6EA8BF2-B10B-4831-8E44-25618D5D6AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dedfc221e2465c4d2c909e7cedf18b51fba44040","datavalue":{"value":{"entity-type":"item","numeric-id":5956771,"id":"Q5956771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$252853EB-321F-4570-8760-EF926B0176F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51d2427facdc42ce1e84dc05815c9d772dbbe37","datavalue":{"value":{"entity-type":"item","numeric-id":4458414,"id":"Q4458414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$1230C781-8B61-46D2-8013-A38D3F72A170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86744b341a111940cccecb2dfadf4e1b45f0d5f6","datavalue":{"value":{"entity-type":"item","numeric-id":3123679,"id":"Q3123679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$40EFFF90-2487-4F78-8C1E-44F3FEC82D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2862b8ea6801c6b14e08ee971727bae6729960d","datavalue":{"value":{"entity-type":"item","numeric-id":1905161,"id":"Q1905161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$4D313294-9991-4668-9401-A6A74328AEF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb9ab485cf13b376fd16dcf2ad87ba7f20a75980","datavalue":{"value":{"entity-type":"item","numeric-id":686525,"id":"Q686525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$CFD49F30-7604-409D-B5F2-1F3DD56A37A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe92f044b290cbdb183578095d6feb108dbf3170","datavalue":{"value":{"entity-type":"item","numeric-id":1812609,"id":"Q1812609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$E8CCCD93-24B0-4B39-BAA6-35E2368DA67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fabbd76998491c35eb30ef82016a0350fec3046","datavalue":{"value":{"entity-type":"item","numeric-id":995589,"id":"Q995589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519798$657020C4-2B64-4DF4-98E5-CC9C42F46616","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"941f1bf8f99a5659fdc7c0dd06dc6b0234b90072","datavalue":{"value":"10.1016/J.EJC.2008.02.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519798$E5CDCC5C-3CEF-4633-A66B-D5CFB0DF79D3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab2165f88ee3b9198826575fb51004ec6e68077f","datavalue":{"value":{"entity-type":"item","numeric-id":2264032,"id":"Q2264032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc5c1668f4787166d89b6a7d767e17c9d2549429","datavalue":{"value":{"amount":"+0.8678683638572693","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":"Q2519798$E77A32A5-EAAE-4E01-9856-212D53092A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e4c447e062bcf6febf73a75c3dc1e2f7649fc50","datavalue":{"value":{"entity-type":"item","numeric-id":1931720,"id":"Q1931720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7ac24e8530da331d0b2857e3d3b062d04c75f5b","datavalue":{"value":{"amount":"+0.8452752232551575","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":"Q2519798$0E5A419C-9171-45B2-B668-EE6F73B18164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae7d288c879da919210717d5c137475d97c15ff4","datavalue":{"value":{"entity-type":"item","numeric-id":648407,"id":"Q648407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2499648d51c002799096d85518ead996effe8a06","datavalue":{"value":{"amount":"+0.8306987285614014","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":"Q2519798$C7966106-2CB3-4944-9E99-AC348C257C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44f685a92e6cfefbe75c61461629411e8247ae1c","datavalue":{"value":{"entity-type":"item","numeric-id":1043813,"id":"Q1043813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d54b1f8165f0dfc124cab3a693bbe9e92bdc2ac","datavalue":{"value":{"amount":"+0.8058760762214661","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":"Q2519798$3F74A82A-C184-49BF-AB5F-C16DCB2D0075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58aefcd0e2e17851c04a22199601d3a7e0b43b53","datavalue":{"value":{"entity-type":"item","numeric-id":608278,"id":"Q608278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa2cffcbfece5244103a52dfa65908844e471d49","datavalue":{"value":{"amount":"+0.7647752165794373","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":"Q2519798$B18EA1CC-CE9F-4807-A896-E87B6C4791F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lit-only sigma game on a line graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lit-only_sigma_game_on_a_line_graph"}}}}}