{"entities":{"Q941391":{"pageid":943239,"ns":120,"title":"Item:Q941391","lastrevid":65575749,"modified":"2026-04-12T03:33:02Z","type":"item","id":"Q941391","labels":{"en":{"language":"en","value":"Connected graphs without long paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321321"}},"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":"Q941391$919E096D-9D20-495D-A110-9BD2F05A4B46","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"beed9178d95290fb2a032628c6d6e175e90811aa","datavalue":{"value":{"text":"Connected graphs without long paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941391$3F95B193-4B36-4386-BC22-0961EFFA8240","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"996d6c4c5cf4a558a70272b666701634d7b47d56","datavalue":{"value":"1159.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$F1D3E4D7-28B0-4B90-A1AA-7F40C8045415","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":"Q941391$C691BD61-9B91-4C2E-B396-907BBED2566F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941391$77A4E179-266F-4F29-8614-0AA32CFA372B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09e37e87a4dbc6ebdd2503562171c39e2a15ba3a","datavalue":{"value":"The authors prove the following result: Let \\(G\\) be a connected graph on \\(n\\) vertices containing no path on \\(k+1\\) vertices, \\(n>k\\geq3\\). Then \\(|E(G)|\\) is bounded above by the maximum of \\({{k-1}\\choose{2}}+(n-k+1)\\) and \\({{\\lceil(k+1)/2\\rceil}\\choose{2}}+\\lfloor(k-1)/2\\rfloor(n-\\lceil(k+1)/2\\rceil)\\). If equality occurs then \\(G\\) is either \\(G_{n,k,1}\\) or \\(G_{n,k,\\lfloor(k-1)/2\\rfloor}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q941391$91B3116F-C0DF-4F0C-A4A7-DD92D74BA86C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$DEF5F3A2-EB73-434D-9124-AD67958D3A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$BBA6D3D3-B5DE-4EC2-831E-88C69531BB1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"47c8d31e610afa7ec06809a9dc7f2f66953ba9b8","datavalue":{"value":"5321321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$44C24C93-DF9E-4975-8B8D-63FBC34D05A2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5b085ded3183023af8db32fe027d8e782bfe876","datavalue":{"value":"extremal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941391$8493FA95-3220-4D14-913A-DCA607CD1B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q941391$D9998DE5-8B39-41EE-BD8D-C4DCEC6EC471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941391$2A4277BA-D55E-4150-AF65-D1A9447C7945","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a33dfe149d6b4e45890139df8b0ab1b5db68bf9","datavalue":{"value":{"entity-type":"item","numeric-id":817615,"id":"Q817615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$C68ED72A-E401-42D5-B7AF-9CE7B77EAABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfaf7e39ce7242df810dc90e03bf20c559cdc99f","datavalue":{"value":{"entity-type":"item","numeric-id":1165243,"id":"Q1165243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$D23CDBD9-B1F8-407B-9145-4078FDE989DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d40587e04768d5f70473e58fb8ddc324137351a9","datavalue":{"value":{"entity-type":"item","numeric-id":185069,"id":"Q185069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$A3E72164-544A-475B-812D-45EA33F6ADDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23be2649b3047d769282fd02a194b75d7b76c1b4","datavalue":{"value":{"entity-type":"item","numeric-id":185070,"id":"Q185070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$56D60A29-39D9-49F7-A550-94C6B949AD14","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4357779dcf19cdb89d5a6057aa8d0856859559aa","datavalue":{"value":{"entity-type":"item","numeric-id":218263,"id":"Q218263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$8CE8F12B-3773-42C1-BA26-F4FC8C093067","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":"Q941391$02265D63-B0A2-4CC9-8706-48214ACC7F49","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"418d21cc85541a6115b603d7a117ac116e532f53","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.08.047","type":"string"},"datatype":"url"},"type":"statement","id":"Q941391$37FF2DD2-D493-4E39-8152-25B92791D0CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67e70e980c680556c9716334328ff10aeee7b9e3","datavalue":{"value":"W2083899663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$4771E2E2-83D9-4FFE-97E2-B97955DFC024","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c4615febf73abeba5acb1543145e5277a39f2ff","datavalue":{"value":{"entity-type":"item","numeric-id":1405126,"id":"Q1405126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$510E861A-243A-4924-94DD-7913258A3464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14dcc9c96f6c72fbc9a4feb8a83dc5eacad8748","datavalue":{"value":{"entity-type":"item","numeric-id":3265306,"id":"Q3265306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$70B40597-D6E3-47B6-ABAB-AB7AC2FB797F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"880b855dcddfd8c396cdb7798c94921288fe1203","datavalue":{"value":{"entity-type":"item","numeric-id":1845890,"id":"Q1845890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$E3584F40-F807-42B0-8501-8C3F8A3A85BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae792a8fab4fc66b71aaca899db75373d0a2b88","datavalue":{"value":{"entity-type":"item","numeric-id":3852213,"id":"Q3852213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941391$D4F3DF66-2247-4308-9986-F9F789837D90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab7a3a44837792db4e7ce57f1561a15640334a68","datavalue":{"value":"10.1016/J.DISC.2007.08.047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941391$CD02842A-5120-41AC-974E-A465A48D5FDB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbdb98cde4b6f145f881a46c366d09bf639e066e","datavalue":{"value":{"entity-type":"item","numeric-id":1379162,"id":"Q1379162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f35804747ecc70160e1246af41c852a5480bbef9","datavalue":{"value":{"amount":"+0.8052849769592285","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":"Q941391$6034B269-7DDB-4522-BE3B-708EF1C4B4E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"209ceb87b52fbd61b7a4c8eb7bf87458e863d237","datavalue":{"value":{"entity-type":"item","numeric-id":554003,"id":"Q554003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1d21319ba2cdd10010f7d372e69546977e99ee","datavalue":{"value":{"amount":"+0.789567232131958","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":"Q941391$43A930E1-8DB1-4DFC-B4F5-89AF63466B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421662f821f3aee5aa33ffc26f9bef5c9aefb7f2","datavalue":{"value":{"entity-type":"item","numeric-id":4542177,"id":"Q4542177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e051216c8dbaca1dad6fa03c80f62cae25f67e9","datavalue":{"value":{"amount":"+0.7893051505088806","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":"Q941391$51BD9B92-EA15-440E-948F-1BF1EC2C4455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"665b135b99478993637f8a9ff493d0e8f2303689","datavalue":{"value":{"entity-type":"item","numeric-id":724883,"id":"Q724883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b14b4e4c90c8c0f0f390e650cec040fd8ebf6f0","datavalue":{"value":{"amount":"+0.7804213166236877","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":"Q941391$E5857453-F933-4E06-9337-0A736B6C7446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"530251b2804a111649469dd25da44f60dc3db0ec","datavalue":{"value":{"entity-type":"item","numeric-id":1186381,"id":"Q1186381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85e361ad2ba0d7bba9ae0f7cad54e0bd98d51844","datavalue":{"value":{"amount":"+0.7802790999412537","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":"Q941391$A0909A14-6728-45FB-9F36-B44A98A6AE1C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Connected graphs without long paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Connected_graphs_without_long_paths"}}}}}