{"entities":{"Q2637738":{"pageid":2648481,"ns":120,"title":"Item:Q2637738","lastrevid":57979299,"modified":"2026-04-03T07:58:40Z","type":"item","id":"Q2637738","labels":{"en":{"language":"en","value":"A Tur\u00e1n-type problem on distances in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6257610"}},"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":"Q2637738$56E277F4-34A9-453A-9B62-0AD224EF7DF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0d1b8656d48bc69f212319f92f696dc3de9eae6c","datavalue":{"value":{"text":"A Tur\u00e1n-type problem on distances in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2637738$B489391F-7B8F-404E-B22C-DE9573D67102","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6bd32155b7d8457da4a8be0c03573f2adb292a5b","datavalue":{"value":"1290.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$E08CE55C-5856-4F68-AA31-A264C9B3611D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"364874cd073b278d91628ba9277910e5c7d3bb39","datavalue":{"value":{"entity-type":"item","numeric-id":322288,"id":"Q322288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$F6CE6D0B-13CB-4632-9C80-12E07AA30925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"164637685440b1603096fbc375dc2f19ea4252ed","datavalue":{"value":{"entity-type":"item","numeric-id":322289,"id":"Q322289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$B994DD01-02D9-4A26-B5D1-2AF1424FBE39","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":"Q2637738$B068B043-4B79-470E-86BF-6DC912687AE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d883e6256eadb2bee0960999c360ea1c12d41b93","datavalue":{"value":{"time":"+2014-02-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":"Q2637738$EB22AD80-12A7-4109-BA4E-C44A8D93AB5F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a54fb719b314098f18532161fcdb1aa6a9b6950b","datavalue":{"value":"https://arxiv.org/abs/1011.2450","type":"string"},"datatype":"url"},"type":"statement","id":"Q2637738$FB7BE208-EF2F-4457-B253-A9C47B8E0AFB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"baf0a00572fbb6e1cfcf9ddb0cb9e7cc2767a518","datavalue":{"value":"This paper studies the question of how many pairs of vertices of distance \\(k\\) a graph on \\(n\\) vertices can have. In other words, given a graph \\(G\\), define the distance-\\(k\\) graph \\(G_k\\) with the vertex set of \\(G\\) and two vertices adjacent if they have distance \\(k\\) in \\(G\\). The problem studied in the paper is to maximize the number of edges \\(e(G_k)\\) of \\(G_k\\) over all graphs \\(G\\) on \\(n\\) vertices.   An earlier result of the first author with Bollob\u00e1s is that when \\(G\\) is restricted to be a tree, then the value of \\(e(G_k)\\) is maximized exactly by certain graphs called brooms. The authors conjecture that, for \\(k\\) and \\(n\\) large enough, also in the general setting brooms maximize \\(e(G_k)\\) and that they are in a sense unique, namely, whenever a graph \\(G\\) maximizes \\(e(G_k)\\) then \\(G_k\\) is isomorphic to the distance-\\(k\\) graph of a broom.  The main result of the paper is to prove the conjecture for the class of graphs with triangle-free distance-\\(k\\) graph. The proof is rather involved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2637738$49A67476-51C4-4A3F-807F-16EDD79E4FEF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"787b1941a844c1f7198d76d44eaf800ed4efd680","datavalue":{"value":{"entity-type":"item","numeric-id":251890,"id":"Q251890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$5B39BA35-8DED-4C0F-8252-3C1D27A75299","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$B7C03094-F3F8-402C-B63B-D618653C66D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$9BCE5C90-9951-4382-826D-7DDAC2FB2477","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e42ed58ca7cacad61c4967e36d2c58f7165c0a35","datavalue":{"value":"6257610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$676A8BED-3B26-4281-9577-1B2E3E8DE248","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0790746f6410ed142073636c3fdda5375d90359","datavalue":{"value":"distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2637738$B0278826-388F-4265-9A62-D8155DD3BABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e64b126034ae97f4a2a7c5558c8347e61afe2ad","datavalue":{"value":"Tur\u00e1n-type problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2637738$90B79F45-4563-410F-ACE5-F8819FC74B66","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":"Q2637738$D523D4C3-A159-420A-98BB-75C1AEBECC75","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"486e8996f30158461186658f853efd0d3bb952c4","datavalue":{"value":"W2045269930","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$BB84BD8F-B56C-4A5B-858F-D33DE337976B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2767b58e368a93ef7a71bdedf7477c53d8db33ba","datavalue":{"value":{"entity-type":"item","numeric-id":4870046,"id":"Q4870046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$C20BA4FA-AB51-4563-A96B-751E1B961DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17ccd441e7bc6a897767e0766251c5cc4bf65e3f","datavalue":{"value":{"entity-type":"item","numeric-id":4166778,"id":"Q4166778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$48F199B7-D0FB-40D2-94A9-A268E1C5088A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad40cf8bc426e5d4fa33e087d30d3451e3f5e88b","datavalue":{"value":{"entity-type":"item","numeric-id":1158165,"id":"Q1158165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$3A6EC86C-D116-4307-872C-308D2673B3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1525e20a7d4629ba065278f0d972b336be9b38fe","datavalue":{"value":{"entity-type":"item","numeric-id":1073050,"id":"Q1073050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$C21B3368-EEFA-4E46-859E-F45F6905B9B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"284bfd1fa4b1cd3c4c5c5989b38010861c527f43","datavalue":{"value":{"entity-type":"item","numeric-id":2713652,"id":"Q2713652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$F56C8F21-BA41-43C3-8C6F-37D2F6FB8A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f878f233476a2906e1851a12c3b560149c275ba","datavalue":{"value":{"entity-type":"item","numeric-id":4780288,"id":"Q4780288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$8A27E3EC-F7C4-4D48-AC50-398225DF9F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b542edbdeb06916683aa5c254f46bb91391d3868","datavalue":{"value":{"entity-type":"item","numeric-id":1874372,"id":"Q1874372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$8B9F2BE6-451E-48FA-8125-746E6631F51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"879e09ea9474957555726ef5b4f6755b267f0f50","datavalue":{"value":{"entity-type":"item","numeric-id":2888879,"id":"Q2888879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$354BF556-5D2C-4849-838F-DFBCD1B45004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38db13a5e54c292e70773362af0d1ab4fbe051f","datavalue":{"value":{"entity-type":"item","numeric-id":5461454,"id":"Q5461454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$F447D889-8DC1-4A28-AB16-DEC385AE63D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9c33ebc6b9acea203c97979ed7cfc76290093b","datavalue":{"value":{"entity-type":"item","numeric-id":532127,"id":"Q532127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$5C689F4E-0AA3-4ED2-8406-B35869A879F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6aab5e152f28626e1882e3d0af920a7c979bb29d","datavalue":{"value":{"entity-type":"item","numeric-id":3470482,"id":"Q3470482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$EBBD3DE8-DBDF-47E8-80CB-942CB8BECE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"732e5eef0b1730e40d935add9a756081e125879d","datavalue":{"value":{"entity-type":"item","numeric-id":2545694,"id":"Q2545694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2637738$D4DAD525-7DA9-404C-A4E8-82EA30658DCD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d2c8f207f8968651c9bfa9b3a0ebe44c5f63c2e","datavalue":{"value":"10.1007/S00373-012-1225-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2637738$A42A616A-FBEE-4A9F-B089-A414FD0B81B0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382fbe301cbe4352b74507d6980d3a4b09174bd8","datavalue":{"value":{"entity-type":"item","numeric-id":331389,"id":"Q331389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82cab9456a1194fdccb3f8bdf3d35d8cd696d43f","datavalue":{"value":{"amount":"+0.9602562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$D5021F94-9948-4B0F-9721-FAD7512274EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8cfd652efee146c02c403af84194a38bd5226d7","datavalue":{"value":{"entity-type":"item","numeric-id":2411797,"id":"Q2411797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47d116c952b4d0f5a91c2639b3ca18dce8f0aa14","datavalue":{"value":{"amount":"+0.9490704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$F2428B3A-05BB-4344-BF5D-8BC30B8B2FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72479f3cb72bbc48b962baffdeaef01591ad9176","datavalue":{"value":{"entity-type":"item","numeric-id":1093651,"id":"Q1093651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abfb0e36bde1fa4c87a0c4d991c55d2f801c473c","datavalue":{"value":{"amount":"+0.91894794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$5C2D0892-6EE0-4C12-87AD-0B912765C3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea4ee979ae2157072c5f2f89242069136c62ff1c","datavalue":{"value":{"entity-type":"item","numeric-id":5827570,"id":"Q5827570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"027f131bf84290a6c20f5face52775873bca2e1a","datavalue":{"value":{"amount":"+0.9180753","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$14A1FA14-1937-4DED-9004-BED015574CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"433a8b2fd163d92a60d615a60ed1e135c9826b0b","datavalue":{"value":{"entity-type":"item","numeric-id":5512796,"id":"Q5512796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e665e7dc04e6c29088bdb8811e30344aba11cdb","datavalue":{"value":{"amount":"+0.9173921","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$5AAA218E-FF22-447A-B28E-BAB52E1C4114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff6bd4fb851cc25f87aa446ba2b7de9669ecc40f","datavalue":{"value":{"entity-type":"item","numeric-id":2039318,"id":"Q2039318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7ff52bd4b172fd89c637d9d1c46da48ae607f8b","datavalue":{"value":{"amount":"+0.91668177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$86601E42-B60C-420F-9FA3-68C71A92917E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e3960a63967df781cae82528b1ae00f8ddcd161","datavalue":{"value":{"entity-type":"item","numeric-id":2632552,"id":"Q2632552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0acc0e325504344c52e1b87746931c94d876f9b","datavalue":{"value":{"amount":"+0.9147386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$9FE10566-8F33-496A-B608-8943C877D8D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d452bc607617a8fa763441241c512de7d310151f","datavalue":{"value":{"entity-type":"item","numeric-id":4677980,"id":"Q4677980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf9cfb5f1bf563d81409db2886803b4b171e4400","datavalue":{"value":{"amount":"+0.91375196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$20678989-171B-4873-ABDA-6A37FF3BCF41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39492b5f336eabf72f7ddc345100bf4f4641ab20","datavalue":{"value":{"entity-type":"item","numeric-id":1297406,"id":"Q1297406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"539bf735c8cbfa40997faf9fae225561fcd0143a","datavalue":{"value":{"amount":"+0.9111995","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$3D61D6AC-A5CD-4A1F-B9BB-D7762794227A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd171d54194494c0b3144760b097c19edca77c4f","datavalue":{"value":{"entity-type":"item","numeric-id":4873210,"id":"Q4873210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c28a23f0830538d3b232af569277e0db97f6ab84","datavalue":{"value":{"amount":"+0.9062922","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2637738$91E99705-FB8D-4215-BF53-177E553784AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2637738","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2637738"}}}}}