{"entities":{"Q1309446":{"pageid":1320196,"ns":120,"title":"Item:Q1309446","lastrevid":68424045,"modified":"2026-04-12T23:37:00Z","type":"item","id":"Q1309446","labels":{"en":{"language":"en","value":"Long cycles, degree sums and neighborhood unions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 473112"}},"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":"Q1309446$11468721-C533-436A-9879-DAE8DD09709F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51f0817d2e19af548b83d46b58f393adbe7e9a1b","datavalue":{"value":{"text":"Long cycles, degree sums and neighborhood unions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1309446$A347798E-9B0A-4B32-AB76-C86B50B588D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fde6f25379c39f412647660a11fd669ebdef9ae3","datavalue":{"value":"0791.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$5379C547-6C97-456D-81EC-153869098F12","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27bcb131eab1e3dca2a64e940af6b57a7d516658","datavalue":{"value":"10.1016/0012-365X(93)90534-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$86483EEE-38B6-4EF7-9CFE-2EF4DC4B333B","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":"Q1309446$87BA56F1-DA89-45AE-8C4A-89EC71319E3B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b439a09488bc2e6cdbf4d00c3a7f90f1bcfc4c1","datavalue":{"value":{"time":"+1994-07-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":"Q1309446$AE38C013-4B8E-460D-99AB-CEB72759A53B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23722e6c2c4d3413e6d094f2ef4a4b2a1fb2778f","datavalue":{"value":"Let \\(\\sigma_ 3\\) denote the minimum degree sum of any 3 pairwise nonadjacent vertices. Let \\(\\text{NC}_ k\\) be the minimum number of vertices in a neighborhood union of any \\(k\\) pairwise nonadjacent vertices. The authors show that every 1-tough graph of order \\(n \\geq 3\\) with \\(\\sigma_ 3 \\geq n+r\\) has a cycle of length at least \\(\\min \\{n,n+\\text{NC}_{r+5+\\varepsilon (n+r)} (G)-\\alpha(G)\\}\\), where \\(\\varepsilon (i)=0,2\\), or 1, accordingly as \\(i \\equiv 0,1\\) or \\(2 \\pmod 3\\), respectively. They also prove that if \\(G\\) is a 1-tough graph of order \\(n \\geq 3\\) with \\(\\sigma_ 3 \\geq n+r\\) and \\(n\\geq 8t-6r-17\\) then \\(G\\) has a cycle of length at least \\(\\min \\{n,2 \\text{NC}_ t(G)\\}\\). Similar results hold for 2-connected graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1309446$999E2BC7-3385-4849-8A47-9ECEFA0B0466","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$DE40FB95-FD3C-40B7-86D4-415ECD98C5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$A6A22A6C-944B-4E66-AD11-295D44C3EBD6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aa983415491427a3921a39f32e5d29b876c5d4d9","datavalue":{"value":"473112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$CB7A1981-F462-444A-BEF2-58C9DA24F31E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c9c5ca69d03be63a7e1998ca3444ee3738a6243","datavalue":{"value":"longest cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1309446$E056C088-D319-43B6-A9EA-A92732040F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91dbf5a5f937fa7dbd877301d6af1c276f0306e5","datavalue":{"value":"hamiltonian cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1309446$5DF2F165-1FBE-487D-8C59-E7585DE8B006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3835ecf46185b926af442cc2b7ac4fafe7516d2","datavalue":{"value":"neighborhood union","type":"string"},"datatype":"string"},"type":"statement","id":"Q1309446$EC268E60-7420-4EF6-8911-1674574C5AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ec37818cbff344e736eaf1ef0870c4588d80a99","datavalue":{"value":"1-tough graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1309446$687083B9-9877-48D1-9C19-971ED3C7D398","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":"Q1309446$111B4889-B474-404A-B839-A01D5433C830","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":"Q1309446$5651D41B-4E71-4896-A92C-51C23D859B94","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":"Q1309446$4B158B0C-8EB6-4286-AB3D-8E759980EF65","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$07348E15-6A1D-4C27-B002-54B420E8DE85","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":"Q1309446$3068B737-EC82-4A17-8F20-35D13A57ED48","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d81eae710083a4cd07751e94f8eb5f21e46e26b","datavalue":{"value":{"entity-type":"item","numeric-id":3971997,"id":"Q3971997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$2B3FE52E-832D-41BE-8266-BD0DBE0D1199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53f08d4ca476fa78909b0bf5fc5875b36368d96a","datavalue":{"value":{"entity-type":"item","numeric-id":1182981,"id":"Q1182981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$0370D62A-F3DD-4F1E-BEFB-9E152AA11049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90cf65a0be1d98fc50fa109c5c3d56393698ce77","datavalue":{"value":{"entity-type":"item","numeric-id":4873795,"id":"Q4873795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$F82DA1E7-D006-43E1-AD18-C3FDC63A024F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7b6f9b4f824c6e8cbb9f7dc37ead7fa403bd8c9","datavalue":{"value":{"entity-type":"item","numeric-id":749553,"id":"Q749553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$A7CB01F0-1E62-414D-BB15-632051C0FF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5ac64eb33ee13002dd16a0225671aee0ee2249","datavalue":{"value":{"entity-type":"item","numeric-id":4192100,"id":"Q4192100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$84990083-3A2F-48F5-8795-932E30D2AD19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$50E65527-5D92-46E1-B7D9-96ED0BCFE090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c80e9c33038c4ac222c23452ea3c5d2e695228","datavalue":{"value":{"entity-type":"item","numeric-id":4014317,"id":"Q4014317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$293F4CFF-06AC-4109-86BE-3E72C3D0D5A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"462a0bc9359525fc6690d3072b5e24da93590e59","datavalue":{"value":{"entity-type":"item","numeric-id":1175978,"id":"Q1175978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$49BDE1C6-D82F-4E21-AB78-1B4208881DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1e88ea96020b3b4e0875e21b4861205a511d18","datavalue":{"value":{"entity-type":"item","numeric-id":4182545,"id":"Q4182545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$BF859458-0443-4483-BE10-FCE050807EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5933bb7e7020e2b54b8600a0cd4f37ea3913bc","datavalue":{"value":{"entity-type":"item","numeric-id":5628163,"id":"Q5628163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1309446$FBA5754E-E0CB-496E-B967-31DE3D229216","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3f07d88672d83935a1c41ab196f82af542924a17","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90534-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1309446$0EBCFD6F-A0B4-4A64-A63B-CD3A3D27C88B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"285a0e4b411993dcb033b35c363b1047ee0008cb","datavalue":{"value":"W1986662362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1309446$70C8DF49-4240-4F68-8B53-B54E7B56DB17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23e310eada736944e7a76597a6ff0af6cf2b2a1c","datavalue":{"value":{"entity-type":"item","numeric-id":4222376,"id":"Q4222376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f65b50022632341ed41ecc2081f86815b0215288","datavalue":{"value":{"amount":"+0.951238751411438","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":"Q1309446$24851EFA-63A8-456F-A061-A8C906F563BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0470f5d1d0342d2e205a32d6dd186a30d4020b19","datavalue":{"value":{"entity-type":"item","numeric-id":4879720,"id":"Q4879720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dd44d50b1f6fcf828fb433c93161ba79f5ce860","datavalue":{"value":{"amount":"+0.9229485392570496","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":"Q1309446$7B72B356-E577-4450-968F-EC57B574C560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b51f456e98404bbce41807e403267790f48628c","datavalue":{"value":{"entity-type":"item","numeric-id":4862113,"id":"Q4862113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfb6dbd575d814111146744039dd579f6e0998f8","datavalue":{"value":{"amount":"+0.8996551632881165","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":"Q1309446$864AAEF4-910C-43DF-AC57-65BD37E25C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ba09a6720c980fe27d105856992e6076073158e","datavalue":{"value":{"entity-type":"item","numeric-id":4030521,"id":"Q4030521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff33219b145866cd62a6fb1742403eb8d2a39584","datavalue":{"value":{"amount":"+0.8992177248001099","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":"Q1309446$739B7214-A0A9-4E97-93D1-94E7B6798F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef178fb8573bdfefd9f1a19b794d604f3e69d112","datavalue":{"value":{"entity-type":"item","numeric-id":1182981,"id":"Q1182981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e94cb2762c5d36b9756e1ad9e4c857e1ce1d95f3","datavalue":{"value":{"amount":"+0.892270565032959","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":"Q1309446$ADE975FE-147B-4B56-B05C-6F8FE1EB4A99","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Long cycles, degree sums and neighborhood unions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Long_cycles,_degree_sums_and_neighborhood_unions"}}}}}