{"entities":{"Q1860929":{"pageid":1871671,"ns":120,"title":"Item:Q1860929","lastrevid":71008740,"modified":"2026-04-13T18:52:39Z","type":"item","id":"Q1860929","labels":{"en":{"language":"en","value":"Algorithmic aspect of \\(k\\)-tuple domination in graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1876796"}},"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":"Q1860929$B3B2CF32-AC38-4ED4-9384-65D8D7C7B624","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"75f385659f2048e730ae78e191dcf0fe81311d65","datavalue":{"value":{"text":"Algorithmic aspect of \\(k\\)-tuple domination in graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1860929$855D0185-76B8-4D02-B7D3-76AD23FAFD39","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39a728e026e8abf8628c7c09324ae1f7d4039c65","datavalue":{"value":"1047.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$97BAA9DD-15C3-41A4-A94F-D84F50EB5338","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27aa2cdc27ddee61a5f22a6acbb5635c6d13fcd4","datavalue":{"value":{"entity-type":"item","numeric-id":247918,"id":"Q247918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860929$BE5475B5-ECAA-47EE-AEC5-9556CF77B2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860929$9C0E8D3D-3BAD-4948-A1A7-22DA1B44E03B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fc770cd89d4fae0e8d7b267c7a43d9a33ef28782","datavalue":{"value":{"entity-type":"item","numeric-id":168175,"id":"Q168175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860929$A4CBCE9F-F000-440D-8D41-1C2FCD67CF05","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c6427ff9a626f686c7f1def93b416dba0b5871b3","datavalue":{"value":{"time":"+2002-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1860929$C81BC9F2-C453-4436-A3B9-56105E67B918","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"763ec24ce02a4177a975351552de860c1d83229f","datavalue":{"value":"A dominating set of a graph \\(G=(V,E)\\) is defined as a set of vertices \\(D\\) such that each vertex from \\(V\\) is adjacent to to some vertex from \\(D\\) or it belongs to \\(D\\). One possible generalization of a dominating set is an \\(M\\)-dominating set. Let each vertex \\(v\\) be associated with a label \\(M(v)=(t(v),k(v))\\), where \\(t(v)\\) is one of the symbols in \\(\\{B,R\\}\\) and \\(k(v)\\) is a nonnegative integer. We say that a set of vertices \\(D\\) is \\(M\\)-dominating if it satisfies the following conditions for all vertices: (M1) If \\(t(v)=R\\), then \\(v\\in D.\\) (M2) \\(\\left| N_{G}[v]\\cap D\\right| \\) \\(\\geq k(v)\\) where \\(N_{G}[v]\\) is the closed neighborhood of vertex \\(v\\). The authors present a linear-time algorithm to find a minimal \\(M\\)-dominating set in a tree with given labelling \\(M\\). In the case when \\(t(v)=B\\) and \\(k(v)=2\\) for all vertices in \\(V\\), the \\(M\\)-dominating set is called \\(2\\)-tuple dominating set or double dominating set. In a graph each vertex is dominated by at least two vertices from a \\(2\\)-tuple dominating set. In the case \\( k(v)=1\\) the \\(M\\)-dominating set is the usual dominating set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860929$CDC5F5AB-484F-42B4-B727-E5E93527C62B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$4CA8793F-7C71-4567-A661-5F6FF844964E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$E000280A-AB9B-4BE9-A85E-4E4795BB759F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cfcc1e65db6bc12da9f1bcfc6742ef4e541ccdae","datavalue":{"value":"1876796","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$D1F446D9-9F99-47C2-8A7D-B2E0B75C6D21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860929$24293919-B3C1-4527-8D31-75C16306A910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3b1d1a9949182529b77fff35c94397a3e0b5b72","datavalue":{"value":"\\(k\\)-tuple domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860929$2A1FD041-C9BC-4707-B337-8A1B568D2166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a49464e2d7be3b5ec6afa9a7b997ccf87f3adaab","datavalue":{"value":"linear algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1860929$0A1921A4-D1FD-42A2-975E-06EEB945F318","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1860929$DAF5D38F-225C-4E47-9273-0315E05521F7","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":"Q1860929$02702FB3-5C20-4C4A-982B-AB13DCF1BED1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"39d23c04cb73da06b86461e02316052283a7e300","datavalue":{"value":"https://doi.org/10.11650/twjm/1500558307","type":"string"},"datatype":"url"},"type":"statement","id":"Q1860929$C3E62DA8-6F99-4FAA-B2D9-165CEBEFAD67","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c69a8aceffabc163daa447f93f301249fa26266","datavalue":{"value":"W4248071256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$7EFF8D32-2A16-4DC4-AD9B-360969C73954","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"64e0d918fc9cd897f68fea93c37e828188790932","datavalue":{"value":"10.11650/TWJM/1500558307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1860929$98EB4B5F-D4A8-4829-B817-19EB0FB73F06","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecd7f45025ff917122e5c6a0547eb4908263c400","datavalue":{"value":{"entity-type":"item","numeric-id":456136,"id":"Q456136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acc12aaa3c798ad94b7e167c43ae391c8bc388d9","datavalue":{"value":{"amount":"+0.97417146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$BFFE4BDE-4673-43F9-87C5-08F0A5DBD1BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef11f0edcc5cbce60b323a879e32f96828730207","datavalue":{"value":{"entity-type":"item","numeric-id":2446334,"id":"Q2446334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d82fc8f28d216b44c2f796c11d40eb23c1aaa78","datavalue":{"value":{"amount":"+0.9408539","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$E5B8D56F-4589-436A-B73B-49C3FCEC1D8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aebc9c047394a08cdf7c32577cfd5cc83b2a12b9","datavalue":{"value":{"entity-type":"item","numeric-id":400524,"id":"Q400524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc6bb0fff97c86ff7734f4eb419826e3a5422715","datavalue":{"value":{"amount":"+0.9370185","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$71F2E439-B1A1-4552-9F31-C72A051B5491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e7e044e52bdf082cb7f633a3724fdb0804c6d93","datavalue":{"value":{"entity-type":"item","numeric-id":1014390,"id":"Q1014390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2364c58edbdae8e22e4d8429db6ee2c180f9762","datavalue":{"value":{"amount":"+0.9354001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$7D94853E-7CC8-42EF-91DF-88D134812619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0de662d88c427188b7ae27b984a0db4ec0010f00","datavalue":{"value":{"entity-type":"item","numeric-id":4247463,"id":"Q4247463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee831e15b5f0da92e54d95cb844eced18cb5be29","datavalue":{"value":{"amount":"+0.9266663","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$D7F75FDF-113B-47E4-ACB3-8217AF2B9D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f1779741a7af8fe204bc058b176f233d0af124a","datavalue":{"value":{"entity-type":"item","numeric-id":2345849,"id":"Q2345849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dafc9f594f92b2357eae245eb4cc9fe97b4270a0","datavalue":{"value":{"amount":"+0.9260732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$F17AD212-2E77-4773-9760-FD332EF64620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d22acd94750aaac44fb2579c1ca314d498592a04","datavalue":{"value":{"entity-type":"item","numeric-id":5002958,"id":"Q5002958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d433b7a989cecf9b7b4962707e2a17aa528960d5","datavalue":{"value":{"amount":"+0.92422324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$7A3E06C0-5962-4FC0-AF1D-34DBD6B2555A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"675aeb5653c35b4ead0cc8dd2b453909d96d2a7e","datavalue":{"value":{"entity-type":"item","numeric-id":708327,"id":"Q708327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c10a803de52a62e6d83ddf5d3a25d348d814d48b","datavalue":{"value":{"amount":"+0.9208249","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$B7D92A1E-52DD-4131-AA9A-570B612B1703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"017e508d4b88c88e2aca5d3b068f1eae4441473c","datavalue":{"value":{"entity-type":"item","numeric-id":5004748,"id":"Q5004748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56ab103d5e07312b97ea39b922da7eeb836046c1","datavalue":{"value":{"amount":"+0.9180626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$1D08C7C1-0692-48FB-8F46-79081E6BA259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38408e3bb08fd27ab49a883165793ff82f1ea320","datavalue":{"value":{"entity-type":"item","numeric-id":5492681,"id":"Q5492681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd9847e63cc4ace0a6ea3045723d1049d221b6db","datavalue":{"value":{"amount":"+0.91542476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1860929$D1E19AFF-14C8-4165-BCF8-F9BAC3B4A52F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithmic aspect of \\(k\\)-tuple domination in graphs.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithmic_aspect_of_%5C(k%5C)-tuple_domination_in_graphs."}}}}}