{"entities":{"Q888585":{"pageid":890433,"ns":120,"title":"Item:Q888585","lastrevid":65140593,"modified":"2026-04-12T00:34:51Z","type":"item","id":"Q888585","labels":{"en":{"language":"en","value":"On the game domination number of graphs with given minimum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6502772"}},"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":"Q888585$6D5F8389-8561-4E43-BDEA-9AC8B77919C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e97eb146431c88680a14fb490cb258522184ed9","datavalue":{"value":{"text":"On the game domination number of graphs with given minimum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q888585$B0380E2C-1A16-455F-8FB6-6B3E24083B82","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"20d3979bd288291974b8d04628bfb7861d91fa38","datavalue":{"value":"1323.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$801ABA6A-1CA2-45DD-9F83-D6510F568E15","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa696e5ef25763a69354b976bf97c62b1e59544c","datavalue":{"value":{"entity-type":"item","numeric-id":279226,"id":"Q279226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$E308270E-A7DB-4644-A7A0-214EFA6385E8","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":"Q888585$95E1F43D-363F-4E06-BC11-2A1F6191D083","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"49c905baf0f1483cbda0527efa721826b9ca8c8f","datavalue":{"value":{"time":"+2015-11-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":"Q888585$39D64D5C-D5B1-4E1C-A7D4-085200C96DDE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b48cad28f49ede8832f7a4c898e3c1e0c0548c5","datavalue":{"value":"https://arxiv.org/abs/1406.7372","type":"string"},"datatype":"url"},"type":"statement","id":"Q888585$327FC63A-A547-42E2-B0FD-AC5F74E299B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"30dfb1529b5893e79fcefb5258b3695bc582db44","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p29","type":"string"},"datatype":"url"},"type":"statement","id":"Q888585$61FFD20C-599F-4F1D-B63F-F3A1FF1A8848","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a982b0d50910a85e19e68e94fd7a298456cfbc80","datavalue":{"value":"Summary: In the domination game, introduced by \\textit{B. Bre\u0161ar} et al. [SIAM J. Discrete Math. 24, No. 3, 979-991 (2010; Zbl 1223.05189)], Dominator and Staller alternately select a vertex of a graph \\(G\\). A move is legal if the selected vertex \\(v\\) dominates at least one new vertex -- that is, if we have a \\(u\\in N[v]\\) for which no vertex from \\(N[u]\\) was chosen up to this point of the game. The game ends when no more legal moves can be made, and its length equals the number of vertices selected. The goal of Dominator is to minimize whilst that of Staller is to maximize the length of the game. The game domination number \\(\\gamma_g(G)\\) of \\(G\\) is the length of the domination game in which Dominator starts and both players play optimally. In this paper we establish an upper bound on \\(\\gamma_g(G)\\) in terms of the minimum degree \\(\\delta\\) and the order \\(n\\) of \\(G\\). Our main result states that for every \\(\\delta \\geq 4\\),   \\[ \\gamma_g(G)\\leq \\frac{15\\delta^4-28\\delta^3-129\\delta^2+354\\delta-216}{45\\delta^4-195\\delta^3+174\\delta^2+174\\delta-216}\\; n. \\]   Particularly, \\(\\gamma_g(G) < 0.5139\\; n\\) holds for every graph of minimum degree 4, and \\(\\gamma_g(G) < 0.4803\\; n\\) if the minimum degree is greater than 4. Additionally, we prove that \\(\\gamma_g(G) < 0.5574\\; n\\) if \\(\\delta=3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q888585$2A30A77C-27A1-4840-9F74-ECE91942C666","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$AA70BD18-4B25-4892-AF35-CE84A9F69556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$C0307267-EDC8-43A5-BD27-1FC2FCB9B484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$60A61ED1-AA20-4A84-A47B-9519ABFA8776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$3353BD31-71BB-493D-B904-D5754ACDCF29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$C2CB15A2-D162-460A-B64B-96C9239B9C39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2371452efa2469ff3edda0f9b37333f801f7e0c1","datavalue":{"value":"6502772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$C080E5C1-DB71-4605-A982-2F26111F8F74","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15af08d22ee001f6ad4442d2f7bcba257ac7379f","datavalue":{"value":"domination game","type":"string"},"datatype":"string"},"type":"statement","id":"Q888585$6B43B02D-9CA1-4F5E-BE7F-981E6ACB588B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16088daa890a158f1c41b7866b3ef82073189664","datavalue":{"value":"game domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q888585$01AC0B7A-47F6-4483-8761-F44A23B67166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ecf09d7c7a42124553f23d9091eacc2c5f2895","datavalue":{"value":"3/5-conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q888585$70E124BA-3590-4E87-A588-219AD98AAD8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q888585$6A9FED33-7590-4B9A-9EC1-B86F915D7B76","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":"Q888585$4C05C099-EB72-45E9-A460-C906A27ACC4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2758f48b1a93e71d851a0e4b14bce521c35fc05","datavalue":{"value":{"entity-type":"item","numeric-id":3503433,"id":"Q3503433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$D7134E04-0601-4131-AF08-C311C96223CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87d7b2de92bbfeaabe712448e8c494f02043a34b","datavalue":{"value":{"entity-type":"item","numeric-id":2017052,"id":"Q2017052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$B93BD070-7AA2-4BAE-90E7-3DBF78B5EF4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e452e7f7b34295c49d58730e1f2a81ec841e255","datavalue":{"value":{"entity-type":"item","numeric-id":2446309,"id":"Q2446309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$C0122174-DE39-4598-9693-4E35F740316E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7739ac8208ceba9d8fe99ba4024578913ec64fdd","datavalue":{"value":{"entity-type":"item","numeric-id":3008021,"id":"Q3008021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$D4CFA9C3-8F9C-48B3-BBC5-7C7680141811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b108e8821c32c1f23a7447e0e1a32772f6d9176","datavalue":{"value":{"entity-type":"item","numeric-id":1946659,"id":"Q1946659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$92C0A4CD-3F82-4A6B-9629-525BC6E66BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e80453928459e2196a712e25ed4b28ee383a707","datavalue":{"value":{"entity-type":"item","numeric-id":2515560,"id":"Q2515560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$794D12D7-20A7-4439-A3F8-BC2410165A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bb993f09a33d7739225061cc0aab6b7f464a299","datavalue":{"value":{"entity-type":"item","numeric-id":468438,"id":"Q468438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$5C669523-E351-4FFD-8166-C41177BC7CB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8ae7c02687d7d1b98de72a018848dec84b806c9","datavalue":{"value":{"entity-type":"item","numeric-id":497340,"id":"Q497340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$6BA9730D-C436-43BC-BBBC-4A67C7B81508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd119daf1d8bfd718f0f07af17844e53c97c97f6","datavalue":{"value":{"entity-type":"item","numeric-id":5408611,"id":"Q5408611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$7C97F1CD-61AE-450B-ABFA-012EBEF3AF65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832ab6c8c5920442c780b2940f9fa09728441ccf","datavalue":{"value":{"entity-type":"item","numeric-id":2251140,"id":"Q2251140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888585$8CBDDE50-3BCB-4E75-A91D-025D7A9CAE5F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"18ae882295d333c97094cef804ba53984d82aba9","datavalue":{"value":"bafkreiey232tq4ozrx66hxazlxruvzqbbg77kf6vbkpjxzzd5v4z5xe2ki","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888585$14D4FBD0-1893-4000-8AFF-0F929A54DC1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e3fdf07e06dfe2bff026041ec7843613616efa0","datavalue":{"value":{"entity-type":"item","numeric-id":3462542,"id":"Q3462542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50dde6c23d4809082b8218d3e6d89ec950381124","datavalue":{"value":{"amount":"+0.9124183058738708","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":"Q888585$88F4641C-FD23-4966-907C-A7D4D1274B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"566aefa0f4c87e68a83225b7e4588cc6228e8ed3","datavalue":{"value":{"entity-type":"item","numeric-id":5279865,"id":"Q5279865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2317a8ae61fce40ca55d4b525caceacad0f35c57","datavalue":{"value":{"amount":"+0.8534026741981506","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":"Q888585$3CAC4C39-3163-42E2-A9A6-261C195BBA10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d059f5fa279be60fb197aee589d4839d8acc93a","datavalue":{"value":{"entity-type":"item","numeric-id":5408611,"id":"Q5408611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de7347d541a961a0280b44d6c3232e168c4cfb74","datavalue":{"value":{"amount":"+0.8506438136100769","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":"Q888585$44D943A8-21FC-4978-B51E-6C1379388C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccbf4641c25eaed3f50e4cb3e8bdf84947c1bd18","datavalue":{"value":{"entity-type":"item","numeric-id":5242939,"id":"Q5242939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8dc3dd6d4e9377f471a5eb3af2d346e919d69f","datavalue":{"value":{"amount":"+0.8425724506378174","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":"Q888585$CD9DAA01-07F2-48D2-A3E3-8FA96ED5593A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b93dc4030564904db4f07aca092b2a3ec9845e2a","datavalue":{"value":{"entity-type":"item","numeric-id":1705814,"id":"Q1705814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"813e7a24540849a2e823ee9363e466c0e85b90cc","datavalue":{"value":{"amount":"+0.8413719534873962","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":"Q888585$3786751D-90BC-46A0-AAFC-4B57F81D3F25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the game domination number of graphs with given minimum degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_game_domination_number_of_graphs_with_given_minimum_degree"}}}}}