{"entities":{"Q1010741":{"pageid":1012589,"ns":120,"title":"Item:Q1010741","lastrevid":50626331,"modified":"2026-01-14T14:56:23Z","type":"item","id":"Q1010741","labels":{"en":{"language":"en","value":"Spanning trees with many leaves and average distance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540938"}},"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":"Q1010741$86CEA52D-2787-437A-947E-AFF66B143DAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf067f0b04f81c2428dea78897203cb76ae1cdd7","datavalue":{"value":{"text":"Spanning trees with many leaves and average distance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010741$F00B9BEF-8CA0-4066-A954-95F687A3E418","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"753b713f3ff653286aa977436eca1adaf16abec2","datavalue":{"value":"1181.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010741$B126DEB3-7427-4C8F-A113-90E01B77DDA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2898476d2281a96e70e1263edf65efdaa3129ebf","datavalue":{"value":{"entity-type":"item","numeric-id":547537,"id":"Q547537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010741$43E59AD7-265B-458E-9DD7-953422A113B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"181a44991ff37502527d2a263ac2d6266a9ea96e","datavalue":{"value":{"entity-type":"item","numeric-id":547539,"id":"Q547539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010741$CF3C105A-95A0-45FF-8CE5-784FB6E3702A","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":"Q1010741$FD1CFA1D-12A6-414E-A72F-4AC3D1E56FE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010741$CD18E7B8-9144-4576-A93F-75A0A0ECA2D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"81c4d5db998ad40a774da646daea9fdfd384976a","datavalue":{"value":"https://eudml.org/doc/117225","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010741$AB4AA9AF-0919-4F48-A2EB-C97B53338CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"301d2f27f6e8d47debd6779c0e83606d481d6b58","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r33.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010741$B30DD03C-3FD3-41CA-8DB3-3DF10D754C1E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"356420f1f69281dff22ccca0df27d6727cebcb9b","datavalue":{"value":"Summary: We prove several new lower bounds on the maximum number of leaves of a spanning tree of a graph related to its order, independence number, local independence number, and the maximum order of a bipartite subgraph. These new lower bounds were conjectured by the program Graffiti.pc, a variant of the program Graffiti. We use two of these results to give two partial resolutions of conjecture 747 of Graffiti (circa 1992), which states that the average distance of a graph is not more than half the maximum order of an induced bipartite subgraph. If correct, this conjecture would generalize conjecture number 2 of Graffiti, which states that the average distance is not more than the independence number. Conjecture number 2 was first proved by F. Chung. In particular, we show that the average distance is less than half the maximum order of a bipartite subgraph, plus one-half; we also show that if the local independence number is at least five, then the average distance is less than half the maximum order of a bipartite subgraph. In conclusion, we give some open problems related to average distance or the maximum number of leaves of a spanning tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010741$E662DF30-C1C1-49C0-954F-131F28E0B0EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010741$99E5404A-1D1F-4EEF-A75F-90F2EC980B56","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f174d3db552db5fc8d1383e67efed6b6ac129c4","datavalue":{"value":"5540938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010741$D4BB96E5-82EB-4864-A77C-92A2E1DEA223","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":"Q1010741$22E8B2F8-7C66-43E4-BE18-8E3C4F82D2EA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9c34a8ec9afeec045b498ca2b69f1ec124e7b226","datavalue":{"value":"bafkreieln4khemzym52tay44qla3hn7cxlycukj424tu5vj6fdmxfksgvu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010741$546B7F4D-54CB-4778-BB9B-882E1D091C32","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb523b1b11ab16edaf426930563c38592f23993","datavalue":{"value":{"entity-type":"item","numeric-id":5495880,"id":"Q5495880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36b8a1157ccc5846fd26ba9ad5d549bfb6d25242","datavalue":{"value":{"amount":"+0.880453884601593","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":"Q1010741$EE68F07C-3BA3-4BE0-85A3-13EF9A5E85AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb1f0a48cbf4b38a4c6c15caa0e303bec6ac66e","datavalue":{"value":{"entity-type":"item","numeric-id":3605159,"id":"Q3605159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb6a3a7e9823d25ea6d4d24eb49b1ef669af9673","datavalue":{"value":{"amount":"+0.8496286869049072","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":"Q1010741$88BA0235-B107-4C6E-8DFA-0768A0C00E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"937adb239e2b672b63c1cb6f40937450fb063ebc","datavalue":{"value":{"entity-type":"item","numeric-id":5477958,"id":"Q5477958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"324f1e50492b21ab37c7302b6466db8cd39e0a88","datavalue":{"value":{"amount":"+0.8410066962242126","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":"Q1010741$D2E73E72-590A-4DD2-9ADF-D2162327A1B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f2f116d4e33d189efb6b1805cb9122b6f771041","datavalue":{"value":{"entity-type":"item","numeric-id":4280250,"id":"Q4280250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d74cc1b8ebf15bc34cef663c58354b53f7de4621","datavalue":{"value":{"amount":"+0.8157991766929626","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":"Q1010741$92857031-0ED9-4202-BFDF-AC2F9D65119A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92eb5873831320444e134f92360b4c7ab7757677","datavalue":{"value":{"entity-type":"item","numeric-id":1930214,"id":"Q1930214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9ab107c5dd8005d14aa2a215c00fe4bd79837fb","datavalue":{"value":{"amount":"+0.8125665187835693","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":"Q1010741$782B4EB7-8325-4076-841A-0AEF0B4EC380","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1010741","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1010741"}}}}}