{"entities":{"Q1124531":{"pageid":1135280,"ns":120,"title":"Item:Q1124531","lastrevid":77756318,"modified":"2026-05-06T09:59:15Z","type":"item","id":"Q1124531","labels":{"en":{"language":"en","value":"Total domination in block graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112410"}},"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":"Q1124531$715DAE73-6DFE-44FC-9E02-CF63819D66D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23e11dfddbb93e7f7d73fc0a3cec805e8e279e1a","datavalue":{"value":{"text":"Total domination in block graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124531$69E20B56-A012-43C5-8A52-46C52328A9A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"120fef62a68753317c09a785e401bfccb2abfa20","datavalue":{"value":"0678.90086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$A89A96B6-57E4-4772-9B8E-7094A28D6D19","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4eb4c4923a176597e7f2b3549cf47cd700235f8","datavalue":{"value":"10.1016/0167-6377(89)90034-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$33FD97D5-0EEF-4FC8-92EE-03C03FCB8FB2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$193362F1-EEC2-419D-93D6-733C7B397F53","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1124531$F0E1AAEF-FA22-46EF-9F74-B85BF20FDE48","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e5339c2715471918205561fd26508deede5437a","datavalue":{"value":"A set of vertices D is a total dominating set for a graph G if every vertex of G is adjacent with at least one vertex in D. Although the problem of determining the minimum cardinality of a total dominating set for an arbitrary graph is NP-complete, polynomial time algorithm are known for certain classes of graphs (e.g. trees, interval graphs). The paper contains an \\(O(| V| +| E|)\\) time algorithm which solves this problem for block graphs. In fact, the algorithm presented here deals with a more general problem which, for particular instances, gives solutions for both domination and total domination problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124531$6994506D-CB2C-48A8-8C70-91F06D58759A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"67aeec512b636e4668aab1b914be3244788dfcae","datavalue":{"value":{"entity-type":"item","numeric-id":914549,"id":"Q914549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$23E975D5-B031-4F83-A524-84C396E817D5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$EEF141F1-9C2D-4C5F-ABA2-3B84D2846DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$8777B1F6-76A2-4749-ABEE-9941578CCF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$E8500DBD-B27E-4F25-9242-2115821297B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$343FC8D2-C015-427E-8ADD-F6DC0BC9BB94","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3bedc38ce270ce3be5a3792fa6d114732eff2c86","datavalue":{"value":"4112410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$ECD1687F-E114-44FA-9296-30CDFE82039C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124531$6DFEB7CA-8266-464A-8D13-5A5A62445AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd16e32548a7088f777df5248fcaea221fee7c4d","datavalue":{"value":"block graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124531$DADCAAEA-6C23-44D0-9592-A63AF126EEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c043eb6b18f919f6025564ffa2fe61a03f5732dc","datavalue":{"value":"total domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124531$BF133F2E-6CB3-45EE-BC4D-4B58B04E1BF0","rank":"normal"}],"P16":[{"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":"Q1124531$4C81A83E-3F07-4BB1-8440-0CEF9CAFBF05","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":"Q1124531$40790538-3FEB-4A0B-92B7-FF4A455B6F01","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d5d630db01630ed76047294d5b400b42e9f3c8d","datavalue":{"value":"https://doi.org/10.1016/0167-6377(89)90034-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124531$7B1100C3-A14B-4A5F-8198-0E5FAA4EACFD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ddd248db5b0af24d8ac5a06bd4531019760e7094","datavalue":{"value":"W2060286450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124531$AF5F5A30-5392-4A22-BBC9-48AE37E99F8D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$663B6D6B-D5E3-40D4-8A81-8493A1B2DAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d207798ab208e2d6135aa6be4f21281e7287368f","datavalue":{"value":{"entity-type":"item","numeric-id":3944643,"id":"Q3944643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$6C462387-29C5-4EBC-91A7-86D85945D8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01090fce27464bb69fad124ed8d1dc368d8d57de","datavalue":{"value":{"entity-type":"item","numeric-id":1171499,"id":"Q1171499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$5567CB19-EFAE-429D-AAD5-8FDF5C5FF5E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b351fad9657df3efe83a4f8f8f50558953cda3","datavalue":{"value":{"entity-type":"item","numeric-id":3697054,"id":"Q3697054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$E17CB1A4-7F15-4BC5-A5A0-6A33F21A6070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e6db8942f273ff1621db889c85dc31d64d70f0f","datavalue":{"value":{"entity-type":"item","numeric-id":3220635,"id":"Q3220635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$6B06A269-F485-4707-B737-8D63A0241087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae7ddb3329597da82f842e9614bf124730cbda4","datavalue":{"value":{"entity-type":"item","numeric-id":1219556,"id":"Q1219556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$46BCF631-8E48-496C-9E01-85E217004FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$5C350162-540D-4B13-AE1F-8AE29CE44D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$00E3BEA0-A56B-4C06-A076-EB34D85770B5","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":"Q1124531$EE4AA16C-9BC3-4AC0-9963-014F60500B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f3a345ac969991571213b2a34fe3bc06c137d18","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$845FF646-E59B-4657-B025-6930F18CF99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd6675c6fd35aca2112b944a189a93b533f77ae","datavalue":{"value":{"entity-type":"item","numeric-id":5903156,"id":"Q5903156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$05BED74F-9A6D-4D5E-8FA9-EB9959E37322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08f81f051fd1e93873019ee9a1d154ca78458d88","datavalue":{"value":{"entity-type":"item","numeric-id":1837213,"id":"Q1837213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$0DFC981D-5E5C-457C-8E0A-B916DA08B4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2f7cee5ab9f468b6c01bc006a2b0b5d8926cdb9","datavalue":{"value":{"entity-type":"item","numeric-id":3791195,"id":"Q3791195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$9E0119C4-A22A-4A21-AAC4-D47F53A81DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ba1d687a45ea9b6660e43c3eb9d43b1d106ece","datavalue":{"value":{"entity-type":"item","numeric-id":3696538,"id":"Q3696538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$1731FDC7-085F-4806-B713-F6E1A6373D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"529339a1eacac1e7414a7c29c7a9dd6e508aef8c","datavalue":{"value":{"entity-type":"item","numeric-id":3688433,"id":"Q3688433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$D9D4E4A0-4FC2-413D-8DF7-92CD5209E8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6a7a007a1f46160063a923727ad34889e92b344","datavalue":{"value":{"entity-type":"item","numeric-id":4119239,"id":"Q4119239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124531$480C0DFB-D5D1-4FB0-826A-2151F9191775","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bae5b3fc815b6bed9722c34a7de0e6f3b8d37c3","datavalue":{"value":{"entity-type":"item","numeric-id":5903156,"id":"Q5903156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6250abfb1f1801a2fb9c51fc1c5a2e816c4ec897","datavalue":{"value":{"amount":"+0.894538938999176","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":"Q1124531$5940415F-7FC1-43D8-8493-836D0724ED5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13744b7c84664d75273503de39dfe7db27131f14","datavalue":{"value":{"entity-type":"item","numeric-id":5903263,"id":"Q5903263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c866502d94f9e6be8873e5298c15103b3ab787b5","datavalue":{"value":{"amount":"+0.8809008002281189","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":"Q1124531$B36AE9F2-47FC-4451-9967-D3F484485EAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"242c43ee174feb29cdd269e3e9549b3564f5520d","datavalue":{"value":{"entity-type":"item","numeric-id":3696538,"id":"Q3696538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f1daaa907d7f1693382d24e3c3d969054d8df77","datavalue":{"value":{"amount":"+0.8788220882415771","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":"Q1124531$020A10BC-DFD9-4F41-B528-0E067D8A7226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94dd2cba351133201ca146c061ce98be975501a7","datavalue":{"value":{"entity-type":"item","numeric-id":3788056,"id":"Q3788056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81d9c444e2a4bbabd0dedbc3dbcae3897c548c60","datavalue":{"value":{"amount":"+0.8471273183822632","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":"Q1124531$FBCAD926-85D5-4D03-A41B-E28A06B71D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e60f3289a8389738ee0a2eb75c13b86f1270b8ad","datavalue":{"value":{"entity-type":"item","numeric-id":5963627,"id":"Q5963627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97670515795a8a5cfa4ac48e9f08c867101711e7","datavalue":{"value":{"amount":"+0.8426124453544617","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":"Q1124531$98C8281F-04B8-42C9-B303-1749093C221B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Total domination in block graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Total_domination_in_block_graphs"}}}}}