{"entities":{"Q2235275":{"pageid":2246018,"ns":120,"title":"Item:Q2235275","lastrevid":73611498,"modified":"2026-04-14T16:39:05Z","type":"item","id":"Q2235275","labels":{"en":{"language":"en","value":"Reducing the domination number of \\(( P_3 + k P_2 )\\)-free graphs via one edge contraction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7412185"}},"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":"Q2235275$9D356EF3-D1C6-4BD5-AC02-C123B5DDB23F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"525ac5ee88fb4ef7c95533839742b145f65e53ef","datavalue":{"value":{"text":"Reducing the domination number of \\(( P_3 + k P_2 )\\)-free graphs via one edge contraction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2235275$DEDA48C2-F346-4197-9927-793A4C06C709","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a037bbc1248c99de7e69a8c8660b308c1381e316","datavalue":{"value":"1479.05263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$F78ABCCF-D5ED-4E5A-91BD-17C9F9AE4B65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"823b4a3050a124d3445026f30d56bdaf7f8e02fc","datavalue":{"value":{"entity-type":"item","numeric-id":2034792,"id":"Q2034792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$F2B30D0A-C36E-4527-A7DE-735B01DA6745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4bd60c5bf8b3bdf5a7ccf7d2d3373c4b573c6b1a","datavalue":{"value":{"entity-type":"item","numeric-id":266809,"id":"Q266809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$0B5612B9-B8E7-47BC-978F-DC4A2E11C96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bb5875e7106e9f5c378ef838caa380176618ea6","datavalue":{"value":{"entity-type":"item","numeric-id":827594,"id":"Q827594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$CB21DE7F-521D-4B32-88F1-44C0EC6D506D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$58AAE1F8-31BF-4DC6-B180-B9F88EA255CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63ea68637f5cfe48b0d0d77e5f0fa82323c89d78","datavalue":{"value":{"time":"+2021-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2235275$3F51E489-3E19-47C2-B8E5-3DDEE39C80F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c22a154509ed7b2af1310c87038e54fa6c8307cc","datavalue":{"value":"https://arxiv.org/abs/2010.14155","type":"string"},"datatype":"url"},"type":"statement","id":"Q2235275$92C3E189-0D0C-42A6-89A5-5434BD8C1E42","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70feda5e551d021812cf2864db5109b81771fe33","datavalue":{"value":"In this paper, the authors reduce the domination number of $G$ using only one edge contraction. The main result shows that the problem is polynomial-time solvable on $( P_3 + k P_2 )$-free graphs for any $k\\geq 0$ which can be combined with former results to obtain a complexity dichotomy of the problem on $H$-free graphs. Moreover, the authors present an algorithm which determines in polynomial time whether $G$ is a Yes-instance of 1-Edge Contraction $(\\gamma)$ or not.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235275$6B7EC4A9-6CEE-46AA-B831-768B54C0470A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f110bc095fac9ab476088ecefa6a0c5a7beeb5ce","datavalue":{"value":{"entity-type":"item","numeric-id":346415,"id":"Q346415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$CF6B70E8-CA52-4885-A69E-EC68196ED7D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$FBE3F968-DD7B-493D-B535-9DD3805CE448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$2916A5C0-8070-40EC-8EF6-08660E347032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$0BB809B9-EE13-417B-9312-DB827D4B3236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$96DF8A82-A1F5-44AA-BF21-63F6AC44CA85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f569359dd41e37f1de129c07700634fe8aa999a","datavalue":{"value":"7412185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$97D34EDD-557F-4E8E-B642-69AA7D957A46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235275$A70B7636-74F2-4DDD-9161-14A5CF6C610F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f60a7d005574d1904e5e8595d3e0199a52832782","datavalue":{"value":"edge contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235275$DD4D52BD-494A-4171-BED5-CEC8EEF468C7","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":"Q2235275$5C39EB47-3978-4C25-AEC4-4B2B5F94B548","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"052bf92bc8f6d1d9a04d32577997614f03df4ecb","datavalue":{"value":"W3202513543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$CDF67B20-9D40-4C97-94E7-46F31ECBEDDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1987744874648e26fcc858e2b40e1ebe6aba037","datavalue":{"value":{"entity-type":"item","numeric-id":5092403,"id":"Q5092403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$0CD065D3-CD4E-4831-8EF3-17E12720ECD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"719eefc5dc37f7ab18ec861de3457ea4b9add418","datavalue":{"value":{"entity-type":"item","numeric-id":3094562,"id":"Q3094562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235275$D5B3E3BC-1558-4470-9B94-083859307AEB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"64f8e8639a7b4da6734c9de821dd6afb1e6d6310","datavalue":{"value":"10.1016/J.DAM.2021.09.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235275$7224981F-5ABD-4D91-9BD6-53F90C84CC45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38bd2db8cf2d1b6f7761ef7e11b150cdbffbb9e5","datavalue":{"value":{"entity-type":"item","numeric-id":2219962,"id":"Q2219962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d98ddbb2d31039fea77ca6e44a8640c3b31c1ec3","datavalue":{"value":{"amount":"+0.8949486613273621","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":"Q2235275$B2A04F90-56F8-4FE4-848B-2225CE25FAEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9cfb39ec1e4061c7dc364a53d010bb7d4d5285b","datavalue":{"value":{"entity-type":"item","numeric-id":2034793,"id":"Q2034793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db8534b4fce59c26f6c492f7eeffa7d5d3ac90f3","datavalue":{"value":{"amount":"+0.8515021204948425","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":"Q2235275$D0F56722-0E03-4CCF-AAF1-156E6C34E41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"169c304e08ad29d5bfa7ae0c6afa767468c0ddc8","datavalue":{"value":{"entity-type":"item","numeric-id":2098176,"id":"Q2098176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5953cbb69e0eacb1c7c7351fbcd776414ed7673f","datavalue":{"value":{"amount":"+0.8372905254364014","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":"Q2235275$9EDDED7E-C658-4D69-9F8B-1C6AA4C40EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ff1d898e4e330d79cbb210722c564109bccc575","datavalue":{"value":{"entity-type":"item","numeric-id":2690876,"id":"Q2690876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8931a5189eeb7cf8103e146215c4e23b96facad6","datavalue":{"value":{"amount":"+0.8311134576797485","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":"Q2235275$0FDEC5F6-992C-4BEA-B745-E76DD8D99F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c585cd9bf5d7a068e15b78285ab2d6d4fbcabc6a","datavalue":{"value":{"entity-type":"item","numeric-id":1784743,"id":"Q1784743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4264a65e7c795877946825edc9eed228ad7d6fd","datavalue":{"value":{"amount":"+0.8082619905471802","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":"Q2235275$4ECF9246-5020-41C3-9BAC-C3FFEDEA1C77","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":"Q2235275$2C5DD427-4A4D-42C2-A8FF-45FE6351BCCF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reducing the domination number of \\(( P 3 + k P 2 )\\)-free graphs via one edge contraction","badges":[]}}}}}