{"entities":{"Q1842153":{"pageid":1852895,"ns":120,"title":"Item:Q1842153","lastrevid":71436579,"modified":"2026-04-13T22:15:17Z","type":"item","id":"Q1842153","labels":{"en":{"language":"en","value":"Majority domination in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 744003"}},"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":"Q1842153$2D186654-32BD-4C56-9C74-A8FE6AAF7923","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"13c47e54e646f7a93621060a42e18e1b00ce3dc8","datavalue":{"value":{"text":"Majority domination in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842153$B2D93BC3-07B0-46A1-B7E2-3FDDCECA2919","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50fc46e3bcd309a56d661044e67fc41be43bb073","datavalue":{"value":"0820.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$314B98BB-1071-41C1-9CC3-3E2F16EAA34F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d8929cae34244050c2969db35f3937b82f0563e","datavalue":{"value":"10.1016/0012-365X(94)00194-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$1C28AD30-8321-4DEF-B7B4-5CA250A55350","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"30e930a9731954d1409834e9686f5365ec717fd0","datavalue":{"value":{"entity-type":"item","numeric-id":270249,"id":"Q270249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$0635D2B1-D431-46EE-8E3F-74898401A5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c676991298a2e76572d5bad759d0f7d75e4fcdc","datavalue":{"value":{"entity-type":"item","numeric-id":281802,"id":"Q281802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$5679DFBB-7590-4FC0-B1A0-0F8DA81D3670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef3efb47b5163e35efff4dde79a3bbdd3dc566b","datavalue":{"value":{"entity-type":"item","numeric-id":186200,"id":"Q186200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$F00CD746-5C11-464C-87A2-225187D12F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7739100a9e4776fc71b00baa4aa296d370394267","datavalue":{"value":{"entity-type":"item","numeric-id":251501,"id":"Q251501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$411147C9-465F-484C-8936-238E6BF17889","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$89C720BD-2360-4271-99A2-277DADB96F4C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2e1b8edebb0fc08f8bdd825ecbb88d46409f4f97","datavalue":{"value":{"time":"+1995-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842153$FEE30CD1-8EA4-4A97-AB60-C706659B1E37","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b3bd500915083a01fc547844c89050a9cb5d53c","datavalue":{"value":"The majority number of a graph is a new numerical invariant of a graph concerning domination; it is defined by means of the majority dominating function. A majority dominating function is a function \\(f:V \\to \\{- 1,1\\}\\), where \\(V\\) is the vertex set of the graph \\(G\\), with the property that for at least half the vertices \\(v \\in V\\) the sum of the values of \\(f\\) in \\(v\\) and in all vertices adjacent to \\(v\\) is at least 1. The sum of the values of \\(f\\) in all vertices of \\(V\\) is called the weight of \\(f\\). The minimum weight of a majority dominating function on \\(G\\) is called the majority domination number of \\(G\\) and denoted by \\(\\gamma_{\\text{maj}} (G)\\). In the paper the values of \\(\\gamma_{\\text{maj}}\\) are determined for some classes of graphs (complete graphs, circuits, etc.) and \\(\\gamma_{\\text{maj}}\\) is related to other numerical invariants concerning domination. It is shown that the problem of deciding, whether there is a majority dominating function of weight \\(k\\) or less (for a given graph \\(G\\) and positive integer \\(k)\\) is NP-complete. Some open problems are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$0D60359C-1556-4A01-8535-B6B4A80BD6FA","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":"Q1842153$E0CA9ECD-C485-4D8E-897B-750460F1954C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$4553BBCA-7946-4EB7-A9A6-9FBE311E3FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$5A677483-BDE1-48B7-8FEB-F07A8154C5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$980C7465-5E6F-45BA-8C7B-6D54E81CD01B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f428b0ca73404e0bcdeba6fc4fed941af69774c6","datavalue":{"value":"744003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$0CFB2F5D-0A3C-4274-BD51-B6836BA443BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfe62c81a3468fe1214ac016026536b94f9d96ba","datavalue":{"value":"majority domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$B249187F-D41C-4F14-ACA1-5E5DD773A60F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02224b10eef52f961574ce460bc1bca74a7ef728","datavalue":{"value":"majority number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$F48D2D5D-6B0B-4BD6-B707-0BF2CAA1FBE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72c7cab09f5a231c76261a1806ea7915f157307a","datavalue":{"value":"numerical invariant","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$3CBB9E2A-5B62-4633-ADBC-E3BAF25E4874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d4df72e45a5d1687c54956789b5ed4af765618c","datavalue":{"value":"majority dominating function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$777EA6A5-5BAB-4C7B-AFFA-F4213DF87A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b589bf7cbbec414fc701694cc759d8ee0fa05aa4","datavalue":{"value":"weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$5185B244-962F-4F46-8157-34DB16523CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85e23f0fa663977dfbaabb27c2d17a6d134bf0ac","datavalue":{"value":"majority domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$21F4BBA5-0128-4BFD-B01E-9DAE51EE90B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842153$8E8BF73E-A836-4E97-9F15-35A766D175BD","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":"Q1842153$92C69657-BC8F-4F50-9FDB-0068DECEB89D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb196da793061969a90a282ec27c55ed2840c398","datavalue":{"value":{"entity-type":"item","numeric-id":4374706,"id":"Q4374706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842153$33B1186E-5CE9-4F9C-8AD6-0A36FDA1AFE6","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":"Q1842153$F5AF9E28-230D-4843-8974-74BF01BE9AE3","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":"Q1842153$7CFC032F-5CB2-49F9-BF1E-9B1E1050F710","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":"Q1842153$818D00E6-AE51-46C6-AEBE-24F48672E87C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"402293c3db4ef4d9cf2fa044380c93fdecb77d6f","datavalue":{"value":"https://doi.org/10.1016/0012-365x(94)00194-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q1842153$AB92E1E4-F155-48E3-B89A-01B78A7856FE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c6a296d4515554e802c2352cff8dc06df093c8c","datavalue":{"value":"W2038457140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842153$C9BF3568-BD01-4D87-B4E1-0E22881AB901","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc69529c7ecca3ccab88c238209c2a41bbb1a224","datavalue":{"value":{"entity-type":"item","numeric-id":5946744,"id":"Q5946744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f996c59668d1cde179b860063c9779179da14ccd","datavalue":{"value":{"amount":"+0.9491822719573976","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":"Q1842153$436AA9C9-D573-447C-A9C1-297B218914BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9193147cddd4e2f177cb528c4610d28b55713780","datavalue":{"value":{"entity-type":"item","numeric-id":2798332,"id":"Q2798332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f996c59668d1cde179b860063c9779179da14ccd","datavalue":{"value":{"amount":"+0.9491822719573976","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":"Q1842153$A8CB7D1A-1563-4DB6-B7CE-BDFD297E205D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35a67650ecad2bfc71b89c1d7594b0c3704f3d28","datavalue":{"value":{"entity-type":"item","numeric-id":4566233,"id":"Q4566233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e28c1e2eb2c429f7ed7b9a293a833b847840cd48","datavalue":{"value":{"amount":"+0.9474200010299684","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":"Q1842153$F1D2BE23-AE0D-4188-8337-862B0AE6AF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e50cd784aeb5608eba811708f85bde9fb7bf1cf4","datavalue":{"value":{"entity-type":"item","numeric-id":1683554,"id":"Q1683554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f14babc9e5be72e6ed1cc3e33c3d580286163eba","datavalue":{"value":{"amount":"+0.9265956282615662","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":"Q1842153$52E560A0-CA76-4AD8-8E95-346400029248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4b3df1edaed578e8ee89475bd0f40db0f099e8f","datavalue":{"value":{"entity-type":"item","numeric-id":5133264,"id":"Q5133264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5806324962121dcde8be7cabd8d33ab2641ee0b","datavalue":{"value":{"amount":"+0.9159822463989258","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":"Q1842153$E3CD6A3E-1E01-4D56-B3C2-BF7340F3BA8A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Majority domination in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Majority_domination_in_graphs"}}}}}