{"entities":{"Q1268112":{"pageid":1278862,"ns":120,"title":"Item:Q1268112","lastrevid":68337519,"modified":"2026-04-12T23:01:47Z","type":"item","id":"Q1268112","labels":{"en":{"language":"en","value":"Maximal trees with bounded maximum degree in a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1211723"}},"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":"Q1268112$0B140100-8708-4D85-AAC0-3466B32CD02B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6358b4a892f39ff359244577c53a60f1e3956b46","datavalue":{"value":{"text":"Maximal trees with bounded maximum degree in a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1268112$9FEB8490-76BE-419E-8A3B-EDC030D33BA4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"560e449f58819acf05863a51fa6dc93915415706","datavalue":{"value":"0911.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$F3023236-795F-4135-AD09-BD19B41AD6CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"711d9b9a3be7de8877fa021149e210e2d961e796","datavalue":{"value":{"entity-type":"item","numeric-id":1268111,"id":"Q1268111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1268112$36F41195-BCCB-4072-BD9E-8A9A4FCC54DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74ebac20d84846a53463f0feda9d1c82c2c24a46","datavalue":{"value":{"entity-type":"item","numeric-id":186285,"id":"Q186285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1268112$67094BF1-A1D8-43FF-B483-E8621BF23F8E","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":"Q1268112$F9D0E2B1-EE70-4359-AD5E-56D9CC884FCB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"139eee8ff9c00f65a123ffdeb076131a6b2c84e0","datavalue":{"value":{"time":"+1998-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1268112$045EBCBD-B895-4B6E-9263-D1E6A6F8A593","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64ce0589314b2e80580f2e9ec991e78e04eb004a","datavalue":{"value":"Let \\(G\\) be a graph with \\(n\\) vertices. \\(d(v)\\) denote the degree of the vertex \\(v\\). It is a native question to discuss the properties of a graph depending on its vertex degrees. For instance, it is well known that \\(G\\) is Hamiltonian if \\(d(v)+ d(w)\\geq n\\) for any pair \\(v\\), \\(w\\) of non-adjacent vertices. Moreover, one of the authors showed, in former times, that if for any independent set of \\(k\\) vertices the sum of the vertex degrees is at least \\(n-1\\), then \\(G\\) has a spanning tree with maximum degree at most \\(k\\).   The paper gives, in the first part, an overview of known results of such kind and reports facts of the size of largest trees with bounded degree. The main part discusses the strengthness of the results and considers all trees with bounded maximum degree which are maximal in \\(G\\). Finally, a generalization of a condition for Hamiltonicity is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1268112$0E2A6EFF-86DC-484C-A3A2-500074D86C38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$FA930651-15E1-4DC3-8892-48269202B920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$A24FB8F6-70DC-42F9-B56D-3CA3B2A49505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$58F272CB-6818-4A3B-A900-ED7A0F52384A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7e06a8d58c40e00e55c901cbd5c0d6764bfb395","datavalue":{"value":"1211723","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$9ADD81E1-8182-46AC-AD8D-EA4FB45D15DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1268112$8572D2B9-5E65-44B6-BC15-E6B5E58B2B00","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1b54857edcab7426c17c1bfaeb67b1f001fa1741","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1268112$8EB99524-3377-40E4-9829-CEB2B02BDF4A","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":"Q1268112$B678BE2A-1075-447B-AC9E-F744ABE0FC30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"922707e87bdf68ebcedfe7c6a7137c796a6f1143","datavalue":{"value":"https://doi.org/10.1007/s003730050027","type":"string"},"datatype":"url"},"type":"statement","id":"Q1268112$27A82AF6-705F-45E8-A59F-0E61B55F2B48","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94e7beef3a455263c1fbf38d0c7071a4ebc88209","datavalue":{"value":"W2003562726","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$65A45FC1-28D7-4A55-BAB4-95FF754D3BCA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6297974f93c7affb99beaf4bce26c7785c7c1cb","datavalue":{"value":"10.1007/S003730050027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1268112$37F7CDC8-03A7-45DE-ADDE-6B82780C2A62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81f81066cfcdde1a135f6d66201c51427d1e3a9c","datavalue":{"value":{"entity-type":"item","numeric-id":5202199,"id":"Q5202199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0a3083a969c324207284695b885136d93f81302","datavalue":{"value":{"amount":"+0.93928933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$6A88FAA3-7392-457B-BF1E-9934FD0F8DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55e7072525b817fd3fd2c8c4cd368a8afb064fec","datavalue":{"value":{"entity-type":"item","numeric-id":5294907,"id":"Q5294907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32db0ba98d005e91c5f82eb18437ae6416c0ab2b","datavalue":{"value":{"amount":"+0.927652","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$8AA24428-231D-4F6D-90FF-4AD05EE99CCB","rank":"normal"},{"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":"ffdef01756116174d08e6e835367a98ce2c0f5f7","datavalue":{"value":{"amount":"+0.9267473","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$C8BDCFFE-910C-4E94-B862-7E6B30193C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae2543f1c41500071ec2bee8a629dcbc6e8bf45d","datavalue":{"value":{"entity-type":"item","numeric-id":3054383,"id":"Q3054383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d12c2e4d5108de84e0ed70351b796bbb0400e68","datavalue":{"value":{"amount":"+0.9189636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$ED343FF5-1D58-48F5-8974-E5188D9BB809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47200d993488c9ce6e07f692b6720bb9d7b75773","datavalue":{"value":{"entity-type":"item","numeric-id":4894608,"id":"Q4894608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e521569dbc850d470682fe8cdbeaf2a27a09666e","datavalue":{"value":{"amount":"+0.9169574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$66E57E8B-EDBE-4C4F-A6F2-997848730797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a5f4330f437f89f362da1f0da892b2292c3f4e3","datavalue":{"value":{"entity-type":"item","numeric-id":4558291,"id":"Q4558291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16341139dc948f94d8d69d15700b6475deb4b7a6","datavalue":{"value":{"amount":"+0.91533923","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$B8269899-C6B9-48B5-B80A-B697C4937779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de10b50777aa2e4fff827d92349452f6b3049b8e","datavalue":{"value":{"entity-type":"item","numeric-id":4288874,"id":"Q4288874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4083cbe2e26e3388bb85c36478df51d6f844d2c9","datavalue":{"value":{"amount":"+0.91261256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$C236F438-772E-4F5C-8BBA-1869DAE058FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1aa5a1bda5e82c440f0e6bf6af1e4c0f36e45215","datavalue":{"value":{"entity-type":"item","numeric-id":396918,"id":"Q396918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb2bc929e9d81f9815096eab55bb05f496f624f6","datavalue":{"value":{"amount":"+0.9117559","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$510DA960-493E-44AB-8B71-0575080D6402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"482a4a3ca337c477ecc24cffeab58facf4cce22c","datavalue":{"value":{"entity-type":"item","numeric-id":1408895,"id":"Q1408895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c9796dc75a40b6414982df356d9846ec389dc9e","datavalue":{"value":{"amount":"+0.9102658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1268112$2C94451A-7D33-4197-9BDD-1E53E81B048B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximal trees with bounded maximum degree in a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximal_trees_with_bounded_maximum_degree_in_a_graph"}}}}}