{"entities":{"Q2366213":{"pageid":2376956,"ns":120,"title":"Item:Q2366213","lastrevid":46345119,"modified":"2025-12-24T14:56:27Z","type":"item","id":"Q2366213","labels":{"en":{"language":"en","value":"Long paths and cycles in tough graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223443"}},"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":"Q2366213$E8CFF7AC-D7F1-40A3-8498-78DA270F782C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c483ae19ce818ecf5c675407945a421a9a090f7","datavalue":{"value":{"text":"Long paths and cycles in tough graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366213$4560CE37-0E91-46AC-BBA3-36AC35B0E313","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dba350bdb0f0ec29901e23022c320f7f4048d9f","datavalue":{"value":"0778.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366213$66D36A3D-3798-4249-BBC7-2427E53C19FE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41d166ce1ed3224c8762bef352249bd07731278c","datavalue":{"value":"10.1007/BF01195323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366213$DBC565B6-AF8A-4E96-AF5A-0CA7B27FB9AA","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":"Q2366213$F236607A-DB77-4A43-B048-C2FD50505BFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366213$23E70BF0-1B07-4CB0-891C-AE1B3CBCC573","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2904a4629f8c40b1a8743bab6f2d5ccada97cd4a","datavalue":{"value":"Denote by \\(p(G)\\) \\((c(G))\\) the length of a longest path (cycle) in the graph \\(G\\). Let \\(\\pi(t,n)\\) \\((\\gamma(t,n))\\) be the minimum of \\(p(G)\\) \\((c(G))\\) over all \\(t\\)-tough \\((t\\)-tough and 2-connected) graphs of order \\(n\\). It is shown that if \\(G\\) is a noncomplete \\(t\\)-tough graph \\((t>0)\\) of order \\(n\\) then  \\[ p(G)+{1\\over\\log(1/t+1)}\\log(p(G)+3)\\geq{1\\over\\log(1/t+1)}(\\log n+1). \\]  Also, if \\(G\\) is a \\(t\\)-tough \\((t>0)\\) 2-connected graph of order \\(n\\) then  \\[ \\log c(G)+\\left({1\\over 2}c(G)-1\\right)\\log\\left({1\\over 2}c(G)- 1+t\\right)-\\left({1\\over 2}c(G)-1\\right)\\log t\\geq\\log n. \\]  Bounds for \\(\\pi(t,n)\\) and \\(\\gamma(t,n)\\) are given. The authors conjecture that, for \\(t>0\\), \\(\\gamma(t,n)\\geq A\\log n\\) for some constant \\(A\\) depending only on \\(t\\). Finally, generalizing a conjecture of \\textit{J. A. Bondy} [Paths and cycles, in \\textit{R. L. Graham}, \\textit{M. Gr\u00f6tschel} and \\textit{L. Lov\u00e1sz} (eds.), Handbook of combinatorics, to appear] for the case \\(l=3\\), it is shown that if \\(G\\) is a 2-connected \\(K_{1,l}\\)-free graph of order \\(n\\) then \\(c(G)\\geq{4\\over\\log(l-1)}\\log n-A\\) for some absolute constant \\(A\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366213$718144D4-D1E4-40E5-83C5-A424CF6094F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366213$3BDB874F-7A31-4CFA-9F90-BD28DF489299","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f0ec2bd05e7d512cde5273bdd09a968c26277e5","datavalue":{"value":"223443","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366213$95512161-F02D-4869-9E3B-D240099E10AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366213$6073EB1B-B0AE-4D84-891C-5EA2429A89B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ebc22d8187ea672fec2c0fc855212abe29ca422","datavalue":{"value":"longest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366213$47BDFBB3-25E9-43D4-9F91-4265AC55EBA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c15cd32c54abc58fde12b9b90b6f282b53cb3156","datavalue":{"value":{"entity-type":"item","numeric-id":339483,"id":"Q339483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$E186EAA9-AD92-4DDC-BAD8-AC2496B7A9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35c8be4e8342e8aed0236bfd0c0eb7f3898c558d","datavalue":{"value":{"entity-type":"item","numeric-id":322313,"id":"Q322313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$6FA54B1B-F628-4951-8C9E-526C01EF2593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba83bed1184d947f193424a3ca00fc169495596b","datavalue":{"value":{"entity-type":"item","numeric-id":968421,"id":"Q968421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$D5D64FCF-ED9F-494B-824D-4FCF56D33881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"098e4ad9b9b171d26caa4b6845dc27c4a8d71de7","datavalue":{"value":{"entity-type":"item","numeric-id":1363685,"id":"Q1363685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$04341139-B11A-4E2E-8C66-3CE357A06E71","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$2964615D-E8F8-47DD-B418-08AF2EED634F","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":"Q2366213$16898948-3A2D-49F5-9AAF-CCB058577290","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de19c043afadec4354a9a63db9e43e6bbe87bc08","datavalue":{"value":{"entity-type":"item","numeric-id":1146693,"id":"Q1146693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$2533A4EA-2CBC-4003-9144-345CFBE69B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$230724FA-0C27-4C51-8CF4-7E3F89575A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$8A8EE2FB-3CCC-4F90-97BD-84146AD4FD3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$0098949A-4F7F-4434-8770-B3FD5D58B2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$B4E66904-1A02-4FC1-A6A6-E531FFDE987E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdd1b8395bb1a08f6f4a613b0e1d9db42613abc1","datavalue":{"value":{"entity-type":"item","numeric-id":1167743,"id":"Q1167743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$D8F9B8A5-FFFC-4704-9C9B-989FF5DD1B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7363ea36466e05a1563486052c8141b433be97f0","datavalue":{"value":{"entity-type":"item","numeric-id":3320427,"id":"Q3320427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$BF5FE320-3B3F-4F7E-8D08-02FE1A5502B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45f392e61bff63209f626f04c695df706b8e939c","datavalue":{"value":{"entity-type":"item","numeric-id":3997887,"id":"Q3997887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$597698D7-847E-472B-9589-CA73685F490D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b17e3335d78bc88e14672e956ecb0f01755df42","datavalue":{"value":{"entity-type":"item","numeric-id":1120590,"id":"Q1120590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366213$1303F495-2E3B-4EC2-80A2-502062E74EE7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9c0b34cbf3659f9b52bd2045eb034ae0a04c44d","datavalue":{"value":"https://doi.org/10.1007/bf01195323","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366213$5973F2F9-4C99-47CA-87F5-A0BF52514F6F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cfb0d8cf0e6e8eb59545d59ec8ac97ee5ad7ed28","datavalue":{"value":"W1981157645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366213$39059AC9-6DC2-49E1-9A08-90A1EB6B9307","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f19e608c2f7d3facbb90624695b85f489725e4d","datavalue":{"value":{"entity-type":"item","numeric-id":4248535,"id":"Q4248535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"845713e898465664dddcc6095fee8c2b1f8a83db","datavalue":{"value":{"amount":"+0.8691046833992004","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":"Q2366213$7072201D-8165-4213-80BB-EAAB7208B83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"188992451b08bfbc1e7f25cadac415fb6cfdbb60","datavalue":{"value":{"entity-type":"item","numeric-id":3139757,"id":"Q3139757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"369078f7a970356257549cb38b6a0f7bba121ddc","datavalue":{"value":{"amount":"+0.8373280167579651","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":"Q2366213$D9EB8293-2883-464E-B728-512F68759C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69386ccdc9bad45c39fe4fbaf7c93856307223a","datavalue":{"value":{"entity-type":"item","numeric-id":1903725,"id":"Q1903725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa23b3be5eb4265c3dd854ab3f312e579264b598","datavalue":{"value":{"amount":"+0.8361945152282715","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":"Q2366213$8A992A8E-0C38-4B74-94F9-4C106DF76321","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366213","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366213"}}}}}