{"entities":{"Q1301655":{"pageid":1312405,"ns":120,"title":"Item:Q1301655","lastrevid":68407212,"modified":"2026-04-12T23:30:12Z","type":"item","id":"Q1301655","labels":{"en":{"language":"en","value":"Restrained domination in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1334477"}},"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":"Q1301655$E3E675DA-BA71-4009-AC9D-8E6C6A961C90","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aaa545c44eb4b04aadc971d5345e673e48ad8e9c","datavalue":{"value":{"text":"Restrained domination in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1301655$0BDF61C9-383F-4AE3-9F6B-EEA5011A5338","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"40a59281c8bb1a0e0a487c3c743663a0dd894778","datavalue":{"value":"1114.05303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301655$0F41CFF5-9229-4A76-AB7E-590F54C3BE7F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65963af58ef6733f3b32fc91998f20173090d127","datavalue":{"value":"10.1016/S0012-365X(99)00016-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301655$1A02A105-9316-4957-8CD8-01BFEC8F1CFF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"087a3606c4133374bbbbd954ecf3dc70077403b6","datavalue":{"value":{"entity-type":"item","numeric-id":1301653,"id":"Q1301653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$142168D3-25BB-4AB1-A24D-4C3BFC1F0C88","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":"Q1301655$1310FAA9-00B8-46E5-9667-A4E9DFCA7380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"22abaee982a81a0b001cdf727d7363834fa3fefd","datavalue":{"value":{"entity-type":"item","numeric-id":1301654,"id":"Q1301654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$6E6A4B94-CA25-4AFF-AE9B-43749B600ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c9d1c9ba6bd3f4aa96f0d37d0211dfaad48b281","datavalue":{"value":{"entity-type":"item","numeric-id":251500,"id":"Q251500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$FF6C98EF-EC66-40AE-9E13-6AF82C3C2105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e651793e9cbddc7ea2f04c3aeb4277840ea96eb","datavalue":{"value":{"entity-type":"item","numeric-id":686247,"id":"Q686247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$2B3CFA7C-ABA3-4600-9E45-4EB8A4751A4B","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":"Q1301655$D87D44AC-7110-474C-9C9E-40BC52B24B1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1fc4aef5934748942375a0bc47ba7404f9f415e","datavalue":{"value":{"time":"+1999-09-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1301655$04D3A197-C2AF-43F7-9478-8E54A5B8CF88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38b309bac4c8e8e0551f8a9e57fb4b2078934ec1","datavalue":{"value":"In this paper, we initiate the study of a variation of standard domination, namely restrained domination. Let \\(G=(V,E)\\) be a graph. A restrained dominating set is a set \\(S\\subseteq V\\) where every vertex in \\(V-S\\) is adjacent to a vertex in \\(S\\) as well as another vertex in \\(V-S\\). The restrained domination number of \\(G\\), denoted by \\(\\gamma_{\\text{r}}(G)\\), is the smallest cardinality of a restrained dominating set of \\(G\\). We determine best possible upper and lower bounds for \\(\\gamma_{\\text{r}}(G)\\), characterize those graphs achieving these bounds and find best possible upper and lower bounds for \\(\\gamma_{\\text{r}}(G)+\\gamma_{\\text{r}}(\\overline G)\\), where \\(G\\) is a connected graph. Finally, we give a linear algorithm for determining \\(\\gamma_{\\text{r}}(T)\\) for any tree and show that the decision problem for \\(\\gamma_{\\text{r}}(G)\\) is NP-complete even for bipartite and chordal graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301655$29549C8B-6EB1-426A-B816-6207393990DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301655$0CF4017F-6D50-4859-A620-218F40017704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301655$07D8A17C-2685-4FBD-BCEA-B78C016C7780","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17726a6b5dec45270ba451edeb9017216376b035","datavalue":{"value":"1334477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301655$F7D550FD-9FA3-4C70-82F6-CC458EBDEB43","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":"Q1301655$9265AF0A-3E99-4C2B-ABEE-01954309BE32","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da3b54f7ef8a2117279ae6dffad9f5ec74f16a9","datavalue":{"value":{"entity-type":"item","numeric-id":3818315,"id":"Q3818315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$700AF68E-AF6D-42A5-879D-B5FA042DC88F","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":"Q1301655$C3A4D4DD-5CDD-4337-80F1-5D1C121D7D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8a879c9e0cec6b492354829e1690102a479089","datavalue":{"value":{"entity-type":"item","numeric-id":5632603,"id":"Q5632603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$278EF947-802C-4EC1-8175-C50355F2F915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"031a6301f7ee8dfe666eef6b4821ffa56b533058","datavalue":{"value":{"entity-type":"item","numeric-id":1200040,"id":"Q1200040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$4497B9DD-CD21-4FD9-8E7F-6C8E3E93878A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39955230987edbd9b04725f49e22d86a615e40b4","datavalue":{"value":{"entity-type":"item","numeric-id":3231818,"id":"Q3231818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$9B4CE0E3-FF26-49B3-A39E-2B71F9836B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66319ecf0caff7d798a39de5750d2791e9e6c56","datavalue":{"value":{"entity-type":"item","numeric-id":3822197,"id":"Q3822197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301655$242CAEB9-358E-4B96-A7F5-672ABB3311E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"951ffa574606b088b56e4cef78e7a2c43f24e8b3","datavalue":{"value":{"entity-type":"item","numeric-id":998423,"id":"Q998423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"675b83ef00c31b646410f96e74a8ec054e08f65b","datavalue":{"value":{"amount":"+0.90279620885849","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":"Q1301655$9D98C932-8427-45B6-BA77-58665F005AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b8c3dd2f6836dde493beb5c467d7fcadd23275c","datavalue":{"value":{"entity-type":"item","numeric-id":3366706,"id":"Q3366706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c7ac6ecdfc23ae295d1e2b3e31abdf7f4bfe771","datavalue":{"value":{"amount":"+0.8991467356681824","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":"Q1301655$C0288F5E-8F78-4BD8-8547-9A1F75C82D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cf43eb039bc7fe65b45b93c15ecafa6fb03853a","datavalue":{"value":{"entity-type":"item","numeric-id":3011735,"id":"Q3011735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f801dc82ab5f858fa5f93e6b6a6ec1d09249795","datavalue":{"value":{"amount":"+0.8864865899085999","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":"Q1301655$B5F3CEA7-FFF5-4F38-A17A-4B58C63CF3E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f30980daa004696f90df532872f377c09f0c99b","datavalue":{"value":{"entity-type":"item","numeric-id":5044530,"id":"Q5044530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9650d2f157393b1dc254e6baf607506d62cb2beb","datavalue":{"value":{"amount":"+0.8808291554450989","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":"Q1301655$593D177B-AF17-483B-9512-F86A56303AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ae15f940706db9f294f3b35cd2fa614aba1d1a2","datavalue":{"value":{"entity-type":"item","numeric-id":3094567,"id":"Q3094567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd6420ea73c0a04f92b66f9fb34595edf30f54f1","datavalue":{"value":{"amount":"+0.8805093765258789","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":"Q1301655$DBF38AE9-3C8F-4D10-9EF5-C4292CFCDFC8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Restrained domination in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Restrained_domination_in_graphs"}}}}}