{"entities":{"Q5928868":{"pageid":8105670,"ns":120,"title":"Item:Q5928868","lastrevid":47594653,"modified":"2026-01-02T04:19:53Z","type":"item","id":"Q5928868","labels":{"en":{"language":"en","value":"Minus domination in small-degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1584465"}},"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":"Q5928868$9ECB9159-9BC0-4CDC-AF99-4326BD62B745","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ce6e2670ea24c423409fe5e66cb9acc067183061","datavalue":{"value":{"text":"Minus domination in small-degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5928868$ECA0586D-DBE7-4C0C-ADBB-301B6FE72D2C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"468fc6a5ed38dcf55e41e1be5d104beca0081a2e","datavalue":{"value":"0971.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928868$106F6B9D-C3FD-4ABC-B099-153492661B0D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9011dd297b3f8bfda4ec28e5b77f4e7d5968b7d7","datavalue":{"value":"10.1016/S0166-218X(00)00219-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928868$814F295D-5F12-4A77-BF07-412175F19F62","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efc35cf3e0639840fea360bd5e9b46c46abc9a77","datavalue":{"value":{"entity-type":"item","numeric-id":169283,"id":"Q169283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$B26DF30B-468C-41A3-8932-FF5EA227D7CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$D211A88E-A1A9-4A09-A24A-9D0102CD108B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d20dfca4b1022c57b939a0be43b6c141588f6ff0","datavalue":{"value":{"time":"+2001-11-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5928868$C57C987B-7AE8-4D4D-B6BB-49AD6EC7B397","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cde829a99837e2dc60dd059f50585a60054af862","datavalue":{"value":"Let \\(G\\) be a graph with vertex set \\(V(G)\\). A mapping \\(f: V(G)\\to \\{-1,0,1\\}\\) is called a minus dominating function on \\(G\\), if \\(f(N[v])= \\sum_{x\\in N[v]} f(x)\\geq 1\\) for each vertex \\(v\\in V(G)\\), where \\(N[v]\\) denotes the closed neighbourhood of \\(v\\) in \\(G\\). The minimum of the values \\(f(V(G))= \\sum_{x\\in V(G)}f(x)\\), taken over all minus dominating functions \\(f\\) on \\(G\\), is called the minus domination number \\(\\gamma^-(G)\\) of \\(G\\). The paper investigates the complexity of computing \\(\\gamma^-(G)\\). It is proved that determinating \\(\\gamma^-(G)\\) is NP-hard for planar graphs with minimum degree \\(\\Delta\\leq 4\\). But in graphs with \\(\\Delta\\leq 4\\) the number \\(\\gamma^-(G)\\) can be approximated within some constant ratio in linear time. Some remrks are added which concern the (similarly defined) signed domination number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928868$E5A61CF7-82C6-4692-A1CF-44AF4B06A571","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$C4720185-C12E-4227-A672-A72759A07995","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928868$5CC44563-BF93-474A-8E77-C5B93CF7DD6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d8b7f765c82a10243976ca3a5697f380e4560c68","datavalue":{"value":"1584465","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928868$D502EF1B-8F90-4F1C-8299-6C68F264757B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae0ed025fe71917d644aca193f9e56aacdbc8715","datavalue":{"value":"minus domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928868$FD249264-A5EA-4A5F-890A-B104CC6E39D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"686acc00f2a546064d6207313e27a4654a895c4a","datavalue":{"value":"complexity of computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928868$2EB518C4-67CE-4A4C-A599-651FAB2F2FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"903069275b9d2a3cf127298a2a93529166b6b2aa","datavalue":{"value":"signed domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928868$C189751C-FEBB-4C22-B619-A58402D5DF6B","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":"Q5928868$4780C22C-145C-4E19-AFED-807C9866E93D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5bf12e645e491838a75e7c029de87127c7444","datavalue":{"value":{"entity-type":"item","numeric-id":5057456,"id":"Q5057456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$2A2F12A1-619E-40C3-9A53-D2614B0134B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3020a9f8f6f5cffbdf41e2eb7fe51465adf388dc","datavalue":{"value":{"entity-type":"item","numeric-id":4268431,"id":"Q4268431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$73D6ABCC-5767-4A1C-B1F0-2DBC4723B2C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c238d4813a46e3061e5b29a6d4f568f76aecd22b","datavalue":{"value":{"entity-type":"item","numeric-id":1917346,"id":"Q1917346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$5D98324E-2E77-4CC7-AE93-E70C6B2410C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1824f0d40c09503dc5fc264b0a313061a8709ea0","datavalue":{"value":{"entity-type":"item","numeric-id":1910590,"id":"Q1910590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$CBCC4129-4F10-421E-84D4-8C41EAA6D1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aacb9fe963971cafe31307ec04405143936415f","datavalue":{"value":{"entity-type":"item","numeric-id":1297430,"id":"Q1297430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$B6104E97-0F08-4731-9D0B-8E72B4AB05AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f97454d602093df36068a2acca31d2227c869523","datavalue":{"value":{"entity-type":"item","numeric-id":4871151,"id":"Q4871151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$525165BB-F3FC-443A-9BC4-69B4D508973A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ecac98bcfd5b0d06ddeb059fceb4e293cd8c17c","datavalue":{"value":{"entity-type":"item","numeric-id":1815329,"id":"Q1815329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$21BD30B7-80C5-4662-94DE-667D9E0DE027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$6DA5266A-719C-41F0-9660-4DD87C455AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb4ac1f01c0aedcd7743e828d35f05afbe5af986","datavalue":{"value":{"entity-type":"item","numeric-id":4033760,"id":"Q4033760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$70FD337E-77DE-4FB4-93EB-5A4822E5E1B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"925d1b8e346d27ab192094a472ecad18dc4a75dc","datavalue":{"value":{"entity-type":"item","numeric-id":4542518,"id":"Q4542518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928868$339BC0CF-FDC1-4CE6-BC79-971168C07954","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df18cae3091ff6a9ff6671b7e9213f14694784fd","datavalue":{"value":{"entity-type":"item","numeric-id":4232774,"id":"Q4232774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e120338f120b8c9d0c65533d4293747a4c91ba37","datavalue":{"value":{"amount":"+0.9356844425201416","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":"Q5928868$CCD70D59-37C0-4298-ADE0-9757BAD0F1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6be22e1affa41af28119778ff273b72ae189626","datavalue":{"value":{"entity-type":"item","numeric-id":1917346,"id":"Q1917346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d1775beea303b01b4ec944a2bda92342fed8f3d","datavalue":{"value":{"amount":"+0.898311197757721","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":"Q5928868$90E5DF4C-95AD-4847-AC9D-20093EF8566C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50266136a55397af54537f02e75bbf69f2375208","datavalue":{"value":{"entity-type":"item","numeric-id":1297430,"id":"Q1297430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37f220406a115056d03bec040ff865b10739f154","datavalue":{"value":{"amount":"+0.8959445953369141","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":"Q5928868$49AAB0B1-7869-4F48-A16C-F63D60300529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54d0b01984f81a21a1334abd0efbcd00f01c3426","datavalue":{"value":{"entity-type":"item","numeric-id":1751171,"id":"Q1751171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbddc4879aa34a103d3f90549d2c1c63fc89524f","datavalue":{"value":{"amount":"+0.8883436918258667","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":"Q5928868$3C95B04C-D517-4E6F-B43F-24F9E2BCB2E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d415de1999126cac65ce963af4d5c768d13441","datavalue":{"value":{"entity-type":"item","numeric-id":2867118,"id":"Q2867118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bac775f917fd4b76acceeb290cdab9518f74af6","datavalue":{"value":{"amount":"+0.8878614902496338","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":"Q5928868$109BEFB4-7939-453B-AAA9-052EFC83131A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5928868","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5928868"}}}}}