{"entities":{"Q2463903":{"pageid":2474646,"ns":120,"title":"Item:Q2463903","lastrevid":50229608,"modified":"2026-01-13T14:23:48Z","type":"item","id":"Q2463903","labels":{"en":{"language":"en","value":"Dominating and large induced trees in regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5218426"}},"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":"Q2463903$119EC9B5-3174-476B-B854-0466584AE0B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b448e15752b0a905b013ee86d6dd6c1ec435a3b","datavalue":{"value":{"text":"Dominating and large induced trees in regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2463903$B5623153-5EAD-4FF0-B5DB-D1298F253F04","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba72535be326ac5bb39a64feeae358316abc35a6","datavalue":{"value":"1127.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$5F756A3B-F89C-4A0B-A4FC-DB53F2A6897A","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":"Q2463903$C5A058CB-4E36-4843-AB36-1498211FC6D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$13DAD32B-CFDB-4B86-9384-110DA375DDAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d0d38ad36a7199bbf27971172c7c13717406fd4d","datavalue":{"value":{"time":"+2007-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2463903$C219241D-6F0E-41F4-A68A-164BF6346B2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"398d470ea9c455ea5d4fab288dcf1053ee9dcd7a","datavalue":{"value":"\\textit{X. Chen} et al. [Ars Comb. 73, 193--203 (2004; Zbl 1112.05317)] asked for characterization of the class of graphs and the class of regular graphs that have an induced dominating tree. The present paper shows that the corresponding decision problems are NP-complete. A forbidden induced subgraph condition is given for the existence of induced dominating trees. Tight lower bounds are given on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2463903$E453EBC0-0B36-4D58-9013-FB523C34C362","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$DF3E39C5-60F2-4E6B-A3A5-7C67074890AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$F8745D45-206D-4027-A5AD-FCEEC59D4397","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97523573cb972ab9df523508cc3561c5b216bc6f","datavalue":{"value":"5218426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$9D7F322C-14F3-4893-886F-0EE76DFCDCD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6863d548c2698d06393bc5489f209f3340bf4a34","datavalue":{"value":"induced dominating tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2463903$3C8E5141-084B-46AC-991D-76044D598B10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2463903$13BC3F3D-1A83-4BDB-BD65-2F2168DE7FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a5106f0b93d1b78fcfbf377f7e671403e33c7e3","datavalue":{"value":"cactus","type":"string"},"datatype":"string"},"type":"statement","id":"Q2463903$EF35E4D5-AB70-49C2-A8C3-5759FDB78411","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"706e08216f8d7e32a9bfdcc84aeeba4ad0f22d8d","datavalue":{"value":{"entity-type":"item","numeric-id":169304,"id":"Q169304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$347F264E-CC3C-483C-85CF-EF687F7656C9","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":"Q2463903$7D541DB6-6CB4-461E-B21E-CF0368771021","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b550dc0248e99b2721430d078bef1f3c2842a5d","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.03.043","type":"string"},"datatype":"url"},"type":"statement","id":"Q2463903$4877E94F-7696-4011-A0C5-933A70B0C487","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4f4dc9c3125959ff0bd4a6e19f285c64557ac22c","datavalue":{"value":"W1986457224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$ADCF71B3-7DEA-48EE-9B0C-AF2D9CBB2BF5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"95dab57fc41351e898b1f1d3b00844ae4d79ce86","datavalue":{"value":{"entity-type":"item","numeric-id":4529530,"id":"Q4529530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$4C71DA74-FE0E-4088-8F48-736F33743EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4093d93707633e5ac92a8edeb9958fbe46aff07","datavalue":{"value":{"entity-type":"item","numeric-id":4337506,"id":"Q4337506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$1E19007D-058F-4705-998C-11529E893D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7977ffb1e5ff72e981863554df401dde6cd8b5aa","datavalue":{"value":{"entity-type":"item","numeric-id":3705470,"id":"Q3705470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$747EED98-6F18-4F98-82CC-EF2F571C675A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b88fba9e6f8178b6ae9e39f799652e71592aa60b","datavalue":{"value":{"entity-type":"item","numeric-id":1406025,"id":"Q1406025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$1C6A9F07-DD02-4234-9AC9-EA033DC32045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e417dbafedd4e8591906a0b6bcc16122265ed939","datavalue":{"value":{"entity-type":"item","numeric-id":5463526,"id":"Q5463526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$03B8E36D-C76B-44F6-9DDA-5B2DE4ABDD92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2688197e4b7aa4f03ae00e8d8d73af8694ddd8","datavalue":{"value":{"entity-type":"item","numeric-id":790843,"id":"Q790843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$CE9E0B53-A701-4377-A968-E501E17B0A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ad64d62d89102920c3c52a8c6730ebd01a66fb4","datavalue":{"value":{"entity-type":"item","numeric-id":4894603,"id":"Q4894603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$F4862651-2D56-4FE1-8401-93049278E8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f459e9c9af6877184140c3302757c4d52b3b99a","datavalue":{"value":{"entity-type":"item","numeric-id":1579559,"id":"Q1579559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$243DAFAC-C7EC-4489-B2BB-10BD280F8154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$E3967531-99FA-407C-AF16-654D0609309C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c464645ad5e6f22f721f51a5c0a439fb090e27e6","datavalue":{"value":{"entity-type":"item","numeric-id":4952178,"id":"Q4952178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$75B88984-EE7C-43D8-B9B5-E6CE4FB05A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2dff358e0f47fee5882e6f1bf6e70cc1f7f452","datavalue":{"value":{"entity-type":"item","numeric-id":1121286,"id":"Q1121286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$AD838319-594C-4940-89FE-24719BBF9FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8d705524fdbfe2e52f105b23cd7e5e22a8d21d8","datavalue":{"value":{"entity-type":"item","numeric-id":1088688,"id":"Q1088688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$1F8818B8-4B9F-4565-9858-DC4AC098A450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7d187221c9e76dd6b8ee7a07dd349be5afe5f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3741633,"id":"Q3741633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$7AAB0156-1879-40BA-86AD-DE0898730B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f7cc95bf9ecef18985f9d57c90c0389960c41a","datavalue":{"value":{"entity-type":"item","numeric-id":3895508,"id":"Q3895508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$A19877D0-6336-41FA-9887-8546F4A7B5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eebfc2c8e646428b4a8df3461b24e4d15cafcbfa","datavalue":{"value":{"entity-type":"item","numeric-id":3804730,"id":"Q3804730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$8D6FE3B3-030C-4A77-A17E-4FCCFDA34F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"486ec6596391c75424fadb4629b8e00052c84b4e","datavalue":{"value":{"entity-type":"item","numeric-id":791532,"id":"Q791532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$2AA92AF5-B6BE-44F1-AB38-64CE0C816055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbad5ef4924c0fe3013b9ffff65d2e0ac671aa6b","datavalue":{"value":{"entity-type":"item","numeric-id":1123898,"id":"Q1123898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2463903$F8B38236-75E5-4A5D-8231-B78561B05353","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fcf0d02b092ded3132884825fd8e67706e656025","datavalue":{"value":"10.1016/J.DISC.2007.03.043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2463903$ADA758A4-8315-423E-9BBB-80F18EAA487F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fe6deecdeb18d62a8b6e6734363fd67ed02ee98","datavalue":{"value":{"entity-type":"item","numeric-id":1082351,"id":"Q1082351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5e546dbd0a449b5959b3c70b754910beda5fcbf","datavalue":{"value":{"amount":"+0.8039430975914001","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":"Q2463903$FAC6179E-3D4F-4611-9249-716D97E3C8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"818066296f8f7357b7adae432d8616d6edf46003","datavalue":{"value":{"entity-type":"item","numeric-id":4944970,"id":"Q4944970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f6ba3aaccaf081503cbbcc5e52f3e56a3b9da43","datavalue":{"value":{"amount":"+0.7680073976516724","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":"Q2463903$B8D3B5E2-EE6E-4935-86F2-B432D3E20554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dcb6e169986475fe7f3e1c55c62f003cb664c7b","datavalue":{"value":{"entity-type":"item","numeric-id":967418,"id":"Q967418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb70b722fb60e7ab6056bf72161272161d14da90","datavalue":{"value":{"amount":"+0.76167893409729","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":"Q2463903$F2752059-37DA-4A9C-97D4-F9B9677FA349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69b68d9e388e0711b7069279819c4fb5b6edaf0b","datavalue":{"value":{"entity-type":"item","numeric-id":2508406,"id":"Q2508406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a298c7b34f2d9e040bb2ae4359cdfa7781a756","datavalue":{"value":{"amount":"+0.7573501467704773","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":"Q2463903$D122AF20-9C29-431E-A1F6-2D8DE7597551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"962cf0b991fc03622973c04ef368323ddad986f4","datavalue":{"value":{"entity-type":"item","numeric-id":5316262,"id":"Q5316262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fcd4a7aaabf15bf5d1ef68ca51953f2eae7d92a","datavalue":{"value":{"amount":"+0.7512640953063965","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":"Q2463903$B76235EB-09D7-4B3A-85AC-3F13C340F09F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2463903","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2463903"}}}}}