{"entities":{"Q2053687":{"pageid":2064429,"ns":120,"title":"Item:Q2053687","lastrevid":57712119,"modified":"2026-04-01T01:09:55Z","type":"item","id":"Q2053687","labels":{"en":{"language":"en","value":"Reconfiguring dominating sets in minor-closed graph classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7435718"}},"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":"Q2053687$C8F91EC7-7D39-473B-B7FE-49E9940DEB21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aadf111e583da3b8f2c26a4a22828057048d500d","datavalue":{"value":{"text":"Reconfiguring dominating sets in minor-closed graph classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2053687$9B982C33-C2D6-47CB-9061-6A8F3EB15A76","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a654c05760e845653d88fefec1faf9838c02cd5c","datavalue":{"value":"1479.05285","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$4971AB6D-345A-4724-B5A8-3AD95F488ED5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a76e14dae6cbb3abcd2d6da25c84b7ddc989b2f","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$1B85D7EC-D55A-4A2E-BFE2-00C5CFE3EB0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1419c1b21e1b9af9ccb7f1d567642d31ddd4142","datavalue":{"value":{"entity-type":"item","numeric-id":2053686,"id":"Q2053686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$E57F180B-7A52-4326-AFF9-83D603E9F44E","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":"Q2053687$5025A5D4-E90B-4B7A-8673-1B32E09BB3F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05b65306975cbdabecb719ac21241bd8d1224360","datavalue":{"value":{"time":"+2021-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2053687$7D1D7461-387A-4AC6-96CC-575C3F0210C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"71e3392a5dc9000168962b1124a081365d322228","datavalue":{"value":"https://arxiv.org/abs/2005.13844","type":"string"},"datatype":"url"},"type":"statement","id":"Q2053687$487C7780-941E-4834-AECA-02B4780ADACA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf61891831443b1ae68329243916616df8ae28c3","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph. A set \\(S\\subseteq V(G)\\) is a dominating set, if every vertex in \\(V(G)\\backslash S\\) is adjacent to at least one vertex in \\(S\\). Given dominating sets \\(S\\) and \\(T\\), is there a sequence of dominating sets \\(S_0 = S_1, S_2,\\ldots, S_k = T\\) such that each \\(S_{i+1}\\) is obtained from \\(S_i\\) by deleting or adding a single vertex? If the answer is yes, then \\(S\\) is said to \\(k\\)-transform to \\(T\\). A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. A graph \\(G\\) of order \\(n\\) has a balanced separator of order \\(k\\) if there is a set \\(D\\) of at most \\(k\\) vertices of \\(G\\) as well as a partition of the vertex set \\(V(G)\\) of \\(G\\) into three sets \\(D,A\\) and \\(B\\) such that \\(|A|,|B|\\leq \\frac{2n}{3}\\), and \\(G\\) contains no edge between \\(A\\) and \\(B\\). The authors prove that there is some positive constant \\(c\\) and there are toroidal graphs \\(G\\) of arbitrarily large order \\(n\\), and two minimum dominating sets \\(S\\) and \\(T\\) in \\(G\\) such that \\(S\\) \\(k\\)-transforms to \\(T\\) only if \\(k \\geq \\max\\{|S|,|T|\\}+c\\sqrt{n}\\). Conversely, for every hereditary class \\(\\mathcal{G}\\) that has balanced separators of order \\(n\\mapsto n^{\\alpha}\\) for some \\(\\alpha<1\\), they prove that there is some positive constant \\(C\\) such that, if \\(G\\) is a graph in \\(\\mathcal{G}\\) of order \\(n\\), and \\(S\\) and \\(T\\) are two dominating sets in \\(G\\), then \\(S\\) \\(k\\)-transforms to \\(T\\) for \\(k = \\max\\{|S|,|T|\\}+\\lfloor Cn^{\\alpha}\\rfloor\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2053687$806BD76E-98C5-433A-9754-836926009D95","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3e5241478eb111c3d7b9249ceb02ff850b9ad819","datavalue":{"value":{"entity-type":"item","numeric-id":277497,"id":"Q277497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$B9C7FFE3-F930-4869-ABC2-E494F36C6CF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$EDFC21A3-4EDE-485E-82E5-0C9F8C99C68A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$F2930753-C9A0-42A1-8EFF-342C33DE8E00","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f6fa4d827e0ce202cbe3e3b71e3aa55f81372e2","datavalue":{"value":"7435718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$60397F8C-A7FC-459C-B236-F3643295415A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2053687$6A92503F-4FD8-4A35-B243-8343EE339798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c3ca57d7e29ab6073aa567c6a395b1f353af0f8","datavalue":{"value":"reconfiguration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2053687$500E36A6-427A-4C4B-9728-F31560E17B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06d9d0201c7071a9c83772de616d279d2cf4cdba","datavalue":{"value":"toroidal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2053687$5AE3B0F6-D792-4A61-8EDC-50C5FE85FF1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2632d2b278e49e7b1997638e97fa5bc770b72fcf","datavalue":{"value":"minor-closed graph class","type":"string"},"datatype":"string"},"type":"statement","id":"Q2053687$69A280CD-6589-4297-AB47-DF45EE3AD78B","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":"Q2053687$34B19F61-DDB9-4FEF-B2D2-76A38D12CD07","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cef7585930390a28e02e17b42d54ee6c3a45cd15","datavalue":{"value":"W3168265398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$B8DF2C5B-4A93-40C1-B6D0-C3FD043CD1D7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3ed914e5873781e39d3e147f52dcbb203dd688c","datavalue":{"value":{"entity-type":"item","numeric-id":2409507,"id":"Q2409507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$3A442353-875A-42BB-9A3F-4A53955654CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41a532391ee9980f7c4c5d979907c0fb733e76c8","datavalue":{"value":{"entity-type":"item","numeric-id":4710963,"id":"Q4710963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$E6534F8E-D8EA-4DE2-9C54-70595D9965CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbb32b7075575c1cb0708f2127f8e393f0d8c07","datavalue":{"value":{"entity-type":"item","numeric-id":3220606,"id":"Q3220606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$CC2C1CCE-1443-4F55-8EDB-B7F9C65CE029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8653897066f3dccd9e0c4c5120870a2c0c06dc3e","datavalue":{"value":{"entity-type":"item","numeric-id":3225132,"id":"Q3225132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$10D48622-D7B2-4988-AC7F-5C5D9E79051C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"872b2794233160ef053c9f1f397d818813b61346","datavalue":{"value":{"entity-type":"item","numeric-id":2014712,"id":"Q2014712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$0198E8D3-1780-4473-8938-167528EB7646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaf34af9062ef3f3cc71a4a0696bf70cac5fcb84","datavalue":{"value":{"entity-type":"item","numeric-id":517018,"id":"Q517018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$928A2949-770E-482F-90BE-8B556647FB0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$3D778970-34B8-4631-BB37-3F81A3187C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc00f68d01a683da71ebdbf42254dc69e2487a1","datavalue":{"value":{"entity-type":"item","numeric-id":2331456,"id":"Q2331456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2053687$BB2789CF-6216-4B3D-891B-FDCA4AFF7BB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"55fe19211756244ef28509e58146a769e366730a","datavalue":{"value":"10.1007/S00373-021-02341-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2053687$27B3BCC8-A455-49CE-B2EB-3B2AB9382694","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"270ce049883d0c83f6842394561a6feecb901b59","datavalue":{"value":{"entity-type":"item","numeric-id":3449837,"id":"Q3449837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a8c09c239be6e1237cc8bd142f0f61d1afa50fe","datavalue":{"value":{"amount":"+0.745287299156189","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":"Q2053687$B7FB6D28-A473-420D-BC6D-FD6437991205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72a3e38ae931f5c608c9194edba6af4630d28bdf","datavalue":{"value":{"entity-type":"item","numeric-id":517018,"id":"Q517018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1db020bc99b0e93385a8708aafe144f1fb617d9c","datavalue":{"value":{"amount":"+0.7430410385131836","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":"Q2053687$DD214988-ABD9-43A4-A492-31798A100A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb2d125565562e0e72749343a9e8aa2480be92e7","datavalue":{"value":{"entity-type":"item","numeric-id":2032965,"id":"Q2032965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4699f98fc7fbc4748c74846cb630dcb141fc85d","datavalue":{"value":{"amount":"+0.7352479100227356","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":"Q2053687$E004A4F6-AE96-45DD-B14D-1C4D333B93E3","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":"Q2053687$7034982A-6E11-4B02-968F-36176B0085E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2053687","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2053687"}}}}}