{"entities":{"Q2159733":{"pageid":2170476,"ns":120,"title":"Item:Q2159733","lastrevid":57477219,"modified":"2026-03-31T02:35:34Z","type":"item","id":"Q2159733","labels":{"en":{"language":"en","value":"Paired domination in trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7566018"}},"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":"Q2159733$657FAC74-D6FF-448C-8C6A-31FE61814696","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac16de81c5080cd4764b673505760b30c361678c","datavalue":{"value":{"text":"Paired domination in trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2159733$556AA78E-E56C-4F98-82BF-677A9D0BB0AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cd94f13bdb360c158053905f92959addbd9b3cb8","datavalue":{"value":"1501.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$BA2564A1-5CAA-4D4E-B78E-34A5366D020D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ce33a91b9f06699fbe67f71c5248a4faa32e796","datavalue":{"value":{"entity-type":"item","numeric-id":785581,"id":"Q785581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$754C11AE-7BA5-4797-ADA4-083B4FE0C8F4","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":"Q2159733$71D5F721-A462-4933-B756-E07BC54628C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f35ec641d2c45a10ec6af9b5b6f5d67fa1e8aa6","datavalue":{"value":{"entity-type":"item","numeric-id":2142696,"id":"Q2142696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$52DF37F0-2FB8-45C4-9777-ABFB0A412D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f71a0ce487c9bb2da56554a416a64948e5c3714d","datavalue":{"value":{"entity-type":"item","numeric-id":396837,"id":"Q396837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$40B9271D-32E6-4778-8FCC-A4B095412512","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$CB6165D9-50DE-49D1-88B6-52BA444662D4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ad9afbe138412ffaaaf6109d22a748c988081a7b","datavalue":{"value":{"time":"+2022-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2159733$793EC5DE-C6BD-4182-BD2A-C49BB34F5866","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c814ec79f453bde5d58bb2689ac2813b0322cf2","datavalue":{"value":"Let \\(G\\) be a graph with no isolated vertex. A paired-dominating set of \\(G\\) is a dominating set whose induced subgraph has a perfect matching. The paired-domination number, \\(\\gamma_{pr}(G)\\), of \\(G\\) is the minimum cardinality among all paired-dominating sets of \\(G\\). We denote by \\(\\gamma(G)\\) and \\(\\gamma_t(G)\\) the domination number and the total domination number of \\(G\\), respectively. \\textit{T. W. Haynes} and \\textit{P. J. Slater} [Networks 32, No. 3, 199--206 (1998; Zbl 0997.05074)] introduced the notion of a paired-dominating set and the paired-domination number of a graph, and they showed that \\(\\gamma(G) \\le \\gamma_t(G) \\le \\gamma_{pr}(G) \\le 2\\gamma(G)\\).  Let \\(T\\) be a tree of order \\(n\\ge2\\). Many results on \\(\\gamma_{pr}(T)\\) have been obtained by several authors, and we list some of them in this review. Let \\(\\Delta\\) denote the maximum among the degrees of vertices, \\(n_i\\) denote the number of degree \\(i\\) vertices, and \\(s\\) denote the number of vertices that are adjacent to some vertices of degree one in \\(T\\).  \\textit{H. Qiao} et al. [J. Glob. Optim. 25, No. 1, 43--54 (2003; Zbl 1013.05055)] provided a linear-time algorithm for computing \\(\\gamma_{pr}(T)\\) and they characterized \\(T\\) satisfying \\(\\gamma(T)=\\gamma_{pr}(T)\\). \\textit{M. Chellali} and \\textit{T. W. Haynes} [AKCE Int. J. Graphs Comb. 1, No. 2, 69--75 (2004; Zbl 1066.05101)] showed that, for \\(n\\ge3\\), \\(\\gamma_{pr}(T) \\le \\gamma_t(T)+ s-1\\) and \\(\\gamma_{pr}(T) \\le \\frac{n+2s-1}{2}\\). \\textit{J. Raczek} [Australas. J. Comb. 34, 343--347 (2006; Zbl 1105.05054)] showed that \\(\\gamma_{pr}(T) \\ge \\frac{n+2-n_1}{2}\\). \\textit{N. Dehgardi} et al. [Filomat 28, No. 3, 523--529 (2014; Zbl 1464.05283)] showed that \\(\\gamma_{pr} (T) \\le \\frac{4a(T)+2}{3}\\), where \\(a(T)\\) is the largest integer \\(k\\) such that the sum of the first \\(k\\) terms of the non-decreasing degree sequence of \\(T\\) is at most the number of edges in \\(T\\).  The authors of the present paper prove that \\(\\gamma_{pr}(T)\\le(\\frac{5\\Delta-4}{8\\Delta-4})n+\\frac{1}{2}n_1+\\frac{1}{4}n_2-(\\frac{\\Delta-2}{4\\Delta-2})\\) and that \\(\\gamma_{pr}(T) \\le 2\\alpha(T)-\\phi(T)\\), where \\(\\alpha(T)\\) denotes the independence number of \\(T\\) and \\(\\phi(T)\\) denotes the maximum cardinality among collections of vertex-disjoint \\(P_3\\)'s (3-paths) each of which contains at least a vertex of degree one in \\(T\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2159733$DFD3A57A-0CB6-4318-944D-CF8E0AD21EDC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dd74384d212cbebff6b299ea4647eddfb8fa5b6","datavalue":{"value":{"entity-type":"item","numeric-id":489730,"id":"Q489730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$9904F7BF-DB3C-46C0-B1F1-9A7A66029DE8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$5758D85F-F869-4839-9109-4F9B916E9C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$58FB4A4A-CB14-4EC9-918A-F5034676C818","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53f06113898498cf59f5e255a59bab1e612ea3e6","datavalue":{"value":"7566018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$ADE32E8C-79FA-4137-89B6-8AFCAC481CC9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ef55a18d71ae581ef91588da40ee03217dce4f6","datavalue":{"value":"paired domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2159733$10002D1F-6180-4A44-8AA6-9AD9E19E5A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2159733$01D07CCE-55D4-4458-A054-B461A5B42DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2159733$C87D9C6B-EEA2-44E1-8504-90D6CC3E9A33","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":"Q2159733$E26FCF12-4133-4F8D-BE9C-77A14DE453D8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d0df8cdceb5fedaf1ae0aeabe9cbbbced546808","datavalue":{"value":"https://doi.org/10.1007/s00373-022-02542-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q2159733$C72113E9-FF12-4337-82FC-A2944D71A425","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5ecb6180f44d3cc12a47ff2b865e7f50778713a1","datavalue":{"value":"W4288826047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$DE6C56DF-757B-4EB0-85A7-BBF207F309E2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1be9f91781cf30883a4ad17e13d56f6f1ce89783","datavalue":{"value":{"entity-type":"item","numeric-id":1773836,"id":"Q1773836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$C8BC9211-EBCD-4445-A63A-79B9012A2516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e85245e225c573bf7eb1337bf3a89b0663536f86","datavalue":{"value":{"entity-type":"item","numeric-id":2975494,"id":"Q2975494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$517411CB-DA7B-4B79-8B64-2500198683C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b88da72b6ad72d0915a0e314bee0d59b6f4ebac","datavalue":{"value":{"entity-type":"item","numeric-id":3384606,"id":"Q3384606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$661E87A0-D410-4F2E-9D49-1ECE603D7881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad5cf18e72a0200cd3dbaf38ed690e1bf93b9d54","datavalue":{"value":{"entity-type":"item","numeric-id":4540077,"id":"Q4540077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$00BFC356-521C-4233-916F-4DB5FA6C0629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19d6a8aed033adf8c47dc6e1ec5b461a5445691b","datavalue":{"value":{"entity-type":"item","numeric-id":4912481,"id":"Q4912481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$A263863F-F3F0-4468-945F-4AD4D66A680C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a11e696a8b88753bafb7a5ad22d294da28f4981","datavalue":{"value":{"entity-type":"item","numeric-id":5487928,"id":"Q5487928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$C1234EAA-2DAA-45AC-9BFF-2F990E6AC975","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1fbd19fd078fcd42728c0f06d55282d02568bac0","datavalue":{"value":"10.1007/S00373-022-02542-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2159733$A5C0EEC3-7AD9-4716-BD6C-3C06EEF44D3F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"286bca1b02e913fda1610b5b844191001fbbb0e3","datavalue":{"value":{"entity-type":"item","numeric-id":1810885,"id":"Q1810885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f60aa98f63903b1cd79b2932de00443e1709567","datavalue":{"value":{"amount":"+0.924524426460266","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":"Q2159733$E87EE4B9-ABC0-429F-B063-64B7B6885714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d33b52c691a82d7a810f9b8921302ff7377fdae","datavalue":{"value":{"entity-type":"item","numeric-id":1773836,"id":"Q1773836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62a2001926f51320658dd4bb683d277be97e183f","datavalue":{"value":{"amount":"+0.9044342637062072","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":"Q2159733$68A0C9D6-7BDF-4A0B-8F65-6F86D19B8AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43209c3f81c7c8f1b1c9e47b26f59521e3316a84","datavalue":{"value":{"entity-type":"item","numeric-id":5487928,"id":"Q5487928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ff7a7653a5768e4a9cde2cfdc63b68f91099300","datavalue":{"value":{"amount":"+0.8999993801116943","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":"Q2159733$C4D7AC72-C0B6-4A45-8CE8-DAAF25F37528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39238b855fffef297f2a298d02408e58316333b7","datavalue":{"value":{"entity-type":"item","numeric-id":3421937,"id":"Q3421937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a91ad77e688e310f77b0840cde5bb5315578e16","datavalue":{"value":{"amount":"+0.8815022706985474","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":"Q2159733$551082D9-406F-4135-835D-B817D33627DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c74e74006e65197270e6ff8dd2e9737bd03f201e","datavalue":{"value":{"entity-type":"item","numeric-id":5492580,"id":"Q5492580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f9ed81b64168ab6d6406c7e4b2b6fa5620704a9","datavalue":{"value":{"amount":"+0.8786312937736511","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":"Q2159733$CB8F3E1E-DBC8-43D0-8972-8D6F417DF991","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2159733$A80A50D9-66AE-442C-AA15-8362D90C3871","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2159733","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2159733"}}}}}