{"entities":{"Q625374":{"pageid":627221,"ns":120,"title":"Item:Q625374","lastrevid":51189953,"modified":"2026-01-17T03:56:17Z","type":"item","id":"Q625374","labels":{"en":{"language":"en","value":"A new bound on the domination number of graphs with minimum degree two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5852462"}},"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":"Q625374$09D55407-D492-4D05-905A-0CFBB0F7DA53","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca3b9f54f9b6c3789871aba82e748c8b4dc45dab","datavalue":{"value":{"text":"A new bound on the domination number of graphs with minimum degree two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q625374$EC0BEF89-C3BE-4F8F-8540-963CD49A8A47","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d774459e2f7197fdf5860ab70af5b51505af5cb8","datavalue":{"value":"1209.05171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625374$A3F27741-AE6D-48A1-BE64-92922F6C4D32","rank":"normal"}],"P16":[{"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":"Q625374$48B1A5D2-64BD-49C5-8A1E-C65AAE35B239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b09124aade2f9a2d1dad9d1d88ddbbb2bdabd00","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625374$D9A1606A-19BE-415B-A83F-FF88126607DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625374$7F6E0D5C-1731-4723-B448-E5E09E537B8F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625374$216377F2-51CD-4FF3-8CB6-B13303D1BB74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94e6b8b6646efe001edd9b80358ba7f0d8e6d8ae","datavalue":{"value":{"time":"+2011-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q625374$1CDBFEED-B4B0-4A68-BB55-3148F96E8BE9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24c96106f24190afc9ca683aa959f56d1d6c85f7","datavalue":{"value":"https://eudml.org/doc/225152","type":"string"},"datatype":"url"},"type":"statement","id":"Q625374$8C7FCA2C-637F-4C0E-820C-1D69B56D8778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"063638726bae0d1eddbf569723855c49864e9266","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p12.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q625374$090BC14C-B764-4607-80B1-77C457AD8237","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"546f9f38eb47749cc1fb883da23ab33996479343","datavalue":{"value":"Summary: For a graph \\(G\\), let \\(\\gamma(G)\\) denote the domination number of \\(G\\) and let \\(\\delta(G)\\) denote the minimum degree among the vertices of \\(G\\). A vertex \\(x\\) is called a bad-cut-vertex of \\(G\\) if \\(G-x\\) contains a component, \\(C_x\\), which is an induced 4-cycle and \\(x\\) is adjacent to at least one but at most three vertices on \\(C_x\\). A cycle \\(C\\) is called a special-cycle if \\(C\\) is a 5-cycle in \\(G\\) such that if \\(u\\) and \\(v\\) are consecutive vertices on \\(C\\), then at least one of \\(u\\) and \\(v\\) has degree 2 in \\(G\\). We let \\(\\text{bc}(G)\\) denote the number of bad-cut-vertices in \\(G\\), and \\(\\text{sc}(G)\\) the maximum number of vertex disjoint special-cycles in \\(G\\) that contain no bad-cut-vertices. We say that a graph is \\((C_4, C_5)\\)-free if it has no induced 4-cycle or 5-cycle. \\textit{B. A. Reed} [Comb. Probab. Comput. 5, No. 3, 277--295 (1996; Zbl 0857.05052)] showed that if \\(G\\) is a graph of order \\(n\\) with \\(\\delta(G)\\geq 3\\), then \\(\\gamma(G)\\leq 3n/8\\).    In this paper, we relax the minimum degree condition from three to two. Let \\(G\\) be a connected graph of order \\(n\\geq 14\\) with \\(\\delta(G)\\geq 2\\). As an application of Reed's result, we show that \\(\\gamma(G) \\leq \\frac{1}{8}\\left(3n+ \\text{sc}(G)+ \\text{bc}(G)\\right)\\). As a consequence of this result, we have that  {\\parindent=7mm \\begin{itemize}\\item[(i)]\\(\\gamma(G)\\leq 2n/5\\);  \\item[(ii)]if \\(G\\) contains no special-cycle and no bad-cut-vertex, then \\(\\gamma(G)\\leq 3n/8\\);  \\item[(iii)]if \\(G\\) is \\((C_4,C_5)\\)-free, then \\(\\gamma(G)\\leq 3n/8\\);  \\item[(iv)]if \\(G\\) is 2-connected and \\(d_G(u)+ d_G(v)\\geq 5\\) for every two-adjacent vertices \\(u\\) and \\(v\\), then \\(\\gamma(G)\\leq 3n/8\\).   \\end{itemize}} All bounds are sharp.","type":"string"},"datatype":"string"},"type":"statement","id":"Q625374$E73CAEDC-1127-4C95-ACCE-5E2A5DF16AEF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625374$8A663234-5948-402B-9030-96DA99250CB5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c6e351228c6204a10844b2f4aabab052abd8640","datavalue":{"value":"5852462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625374$2BB344F1-408D-4C7D-B76C-A6208D907873","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b77b431fc86a92792dc6a21fc772bba2088fb678","datavalue":{"value":"bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q625374$BBE2EDEC-0AA3-4370-A745-D717E3A479A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q625374$B89025EE-B666-4E35-88C4-5A5C5EFA4490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q625374$0A48F767-13C3-47BB-97CE-E1DF48390C16","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":"Q625374$F6118785-1C46-4378-AC2C-221B7FDB54A9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a07b6f2363a98089d9b309e63cbca0708adb6b15","datavalue":{"value":"bafkreicbqgm3hkpzzeuxibdknsjlbmi3etg6yupagt22uiywrrf57o2cqu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625374$7B7100B0-E6B7-402F-9831-28BC6CF0B1CF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57a5be11ca6df811ddd60dded942024810bf252f","datavalue":{"value":{"entity-type":"item","numeric-id":1011694,"id":"Q1011694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53a692ad2a5885291e37e65dc589490e87c590fb","datavalue":{"value":{"amount":"+0.9072346687316896","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":"Q625374$162E1EFE-E6F9-49E3-A127-02A23693C09E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e59a29ea32b6ff49668b68c0661462cce1bfdbf","datavalue":{"value":{"entity-type":"item","numeric-id":3490039,"id":"Q3490039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc8f32ade60b6015b10d063c7704a54f6b681825","datavalue":{"value":{"amount":"+0.8776407241821289","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":"Q625374$BF91E1A2-685A-4776-8A6F-6AA1D42F14C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d20e4d5dcf9a57f05ab3d2088d7d0c520a3e8e8","datavalue":{"value":{"entity-type":"item","numeric-id":839753,"id":"Q839753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb81597b012af8fe57717bd7aa1e635057b2945","datavalue":{"value":{"amount":"+0.8566875457763672","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":"Q625374$13093B79-2A3E-4D65-B14A-5295C71C9BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cd7600156aafb0796c641b8b6d846f95d2295e4","datavalue":{"value":{"entity-type":"item","numeric-id":5461690,"id":"Q5461690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"430cd1acbd0d3b6c06a61ad5e347cedb628ad6ff","datavalue":{"value":{"amount":"+0.8406122326850891","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":"Q625374$6F37B0E1-E058-458F-9E81-0315663A17A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ec0e58f3732e8a2fb2e9f272ef11041ace73c4b","datavalue":{"value":{"entity-type":"item","numeric-id":2656332,"id":"Q2656332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70a33bf00c49c3f7aab499dc59ed926b1e4f2a34","datavalue":{"value":{"amount":"+0.8370348215103149","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":"Q625374$57DA5AB4-D17B-43B6-8404-6AD0FDEB5890","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:625374","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:625374"}}}}}