{"entities":{"Q5946744":{"pageid":8123546,"ns":120,"title":"Item:Q5946744","lastrevid":41966751,"modified":"2025-05-19T20:18:24Z","type":"item","id":"Q5946744","labels":{"en":{"language":"en","value":"On majority domination in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1659491"}},"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":"Q5946744$5C16E701-E54D-4E35-A0F6-D01309C45301","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b9f6952facc08de0a0dec77e176c5a5fa23d8d1","datavalue":{"value":{"text":"On majority domination in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5946744$41CEDE97-BC10-4F24-BD4A-6C674871EE39","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c8fbb2e6e9171ce58b97f3fedee5fde808001b27","datavalue":{"value":"0982.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$72C26E30-E4F6-4AF2-B701-9FA9FAFBAC9E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5757e09022120f3a57fed09b23c79db6dec349fa","datavalue":{"value":"10.1016/S0012-365X(00)00370-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$44F0AF53-4848-4E5D-9E0D-2B4A5F55B7C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f045e26a9f9b9278b1bc8e30a4ebd216fae5ec6","datavalue":{"value":{"entity-type":"item","numeric-id":208176,"id":"Q208176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946744$CB7B9F6E-3134-4CE8-B9E1-7994F78A3810","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":"Q5946744$ED9ABDF3-F5B9-4AD1-AB9B-0A1EE6A2B7F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"09a65dcece05039203ce03236409dca56b9f1271","datavalue":{"value":{"time":"+2002-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5946744$B357111B-10D9-4C7C-97CD-688D5CA583E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"94626be276206b45b57e94a7e29516fb1870dd91","datavalue":{"value":{"entity-type":"item","numeric-id":190550,"id":"Q190550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946744$8C2F1EF6-29B3-4799-9972-50238DF86CFE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$267F0956-5CEC-4F1D-8B89-8F270959CEE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$B7C9F993-C662-4BE0-A174-D01D3C52C121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$06C84765-CF9F-483C-B61E-C69BC2D0B038","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9586aa30197676dad466723dbb9e8cf73b66626e","datavalue":{"value":"1659491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$09F15BB5-C8E4-46E5-BD2D-8F3599420118","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfe62c81a3468fe1214ac016026536b94f9d96ba","datavalue":{"value":"majority domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946744$9AB8041F-8835-4BC3-A414-63D159E8B590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946744$7D72AB6B-4AF3-453B-A77F-040314068EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191403835f9d573ead779b7e37a9e1db540852cc","datavalue":{"value":"extremal problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946744$E4A2C98A-9922-4479-BA46-E45114AE7AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946744$4EC0DFBE-216E-4F40-838F-52317724E8C8","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":"Q5946744$0B3CD14A-C9EE-43C7-8254-040967B0EEA4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bbd69c2b36139975048e57527771e66129f4f640","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00370-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q5946744$A9EC96CB-258A-4AFD-8F49-EE9530C6AAC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e620ae2138671e25c3bfd036bd8edd7b9aae00b7","datavalue":{"value":"W2011180679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946744$4B7A3C72-B78E-4663-BFDB-96AD97621DC5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d745e3be2e25666047bba757e8003faac2d2593","datavalue":{"value":{"entity-type":"item","numeric-id":1842153,"id":"Q1842153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaf2bab95ba848b794bf91580be9b0cf7c99bb51","datavalue":{"value":{"amount":"+0.89032274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$21F2A9B9-9E9C-40A5-903D-218D62F676C9","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":"4fe55d3d1ea5a93229c44925f96f3bcdf98a95d2","datavalue":{"value":{"amount":"+0.8536273","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$7BE234E8-3469-447B-B9AB-6B36B27EA963","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":"1969fef64d3f4710772ae8ddeeae5e1141df97ae","datavalue":{"value":{"amount":"+0.8528724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$9DEAF434-F1B6-4ECD-B241-B2481D3211C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7217ec8ed3184523ff44521ec3659192ee17b82","datavalue":{"value":{"entity-type":"item","numeric-id":5133113,"id":"Q5133113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1969fef64d3f4710772ae8ddeeae5e1141df97ae","datavalue":{"value":{"amount":"+0.8528724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$A0F610B2-5835-4D54-8BA3-CA4B1CA9E430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9f49505822c2fe7ff8e8141e7e209ed9d6dac0d","datavalue":{"value":{"entity-type":"item","numeric-id":4552219,"id":"Q4552219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"056fca8d823bcc6a0ca8e6752b0ebfb5c2201fa4","datavalue":{"value":{"amount":"+0.8448023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$AF1CD9DC-8ABD-451A-9FA4-91A3A40A7390","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":"0dd849c60ad8c8a9cdffb049b9d0e975c8e2f26f","datavalue":{"value":{"amount":"+0.84420025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$26287018-7774-4FD4-A842-60670E1825BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b09c0c4b0d8b4407e82170e1d1bef8ef0ed19573","datavalue":{"value":{"entity-type":"item","numeric-id":1371054,"id":"Q1371054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa5334de4af0a55399bd77282a4687e04f6b9f18","datavalue":{"value":{"amount":"+0.8348644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$2DC598C3-12CE-411D-9897-2F0F7A94ACC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ef5029ea33b1b6420bbf66486063473737bb4f6","datavalue":{"value":{"entity-type":"item","numeric-id":5269450,"id":"Q5269450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd52004736c276b0dd15a5f0e163e3c8a1e33bab","datavalue":{"value":{"amount":"+0.83057076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$BD8F77AC-3A72-4DE4-B451-3D23279D4B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83261446118cddc173e9718074f26a1223074bb7","datavalue":{"value":{"entity-type":"item","numeric-id":3384120,"id":"Q3384120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"379a51078ccb48aee573c1052827c8ae22de5854","datavalue":{"value":{"amount":"+0.8059988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$326A3E23-7557-45E8-A6CD-ACA5EEA78251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"902d28564f86d4a937366d3d807d7b129df7c001","datavalue":{"value":{"entity-type":"item","numeric-id":4374702,"id":"Q4374702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d71f7500b04e2b8c5d8a11ed84353d29957ecdc5","datavalue":{"value":{"amount":"+0.8031877","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5946744$C95E3740-7CA6-452D-A6C2-D2704D6A9092","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"54415d7be7c38d385ad4000c6dc48bcea5c2eca2","datavalue":{"value":"A majority dominating function on the vertex set of a graph \\(G=(V,E)\\) is a function \\(g\\colon V\\mapsto\\{1,-1\\}\\) such that \\(\\sum_{u\\in N[v]} g(u) \\geq 1\\) for at least half of the vertices \\(v\\) in \\(V\\). The majority domination number \\(\\gamma_{\\text{maj}}(G)\\) of a graph \\(G\\) is defined as NEWLINE\\[NEWLINE \\gamma_{\\text{maj}}( G)=\\min \\left\\{\\sum_{v\\in V} g(v): g\\text{ is a majority dominating function on }V\\right\\}. NEWLINE\\]NEWLINE The majority domination number has been determined for certain families of graphs in \\textit{I. Broere} et al. [Discrete Math. 138, No. 1-3, 125-135 (1995; Zbl 0820.05037)]. Using different counting technique the author generalizes results from the above-mentioned paper and determines \\(\\gamma_{\\text{maj}}(G)\\) for some other families of graphs, mostly composed of complete graphs and their complements. NEWLINENEWLINENEWLINEIn the above-mentioned paper, it has also been shown that the problem of deciding whether \\(\\gamma_{\\text{maj}}(G) \\leq k\\) for a given graph \\(G\\) and positive \\(k\\) is NP-complete. Here the author shows that the problem remains NP-complete even when \\(G\\) is the disjoint union of complete graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946744$C3BF5D3D-EB9E-40FC-B4F9-80B2D390115E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5946744","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5946744"}}}}}