{"entities":{"Q687919":{"pageid":689768,"ns":120,"title":"Item:Q687919","lastrevid":63619293,"modified":"2026-04-11T14:23:45Z","type":"item","id":"Q687919","labels":{"en":{"language":"en","value":"Long cycles in 1-tough graphs with large degree sums"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 436768"}},"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":"Q687919$A867A2C0-A653-4D8B-96C3-61573A2C2E0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4dba12c0049eb9b8b5daea34ad901c046637f3cb","datavalue":{"value":{"text":"Long cycles in 1-tough graphs with large degree sums","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q687919$DD46B40B-51FC-463B-9DC4-5B076C819355","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d718303a85f24da996fc4b8599d52e374b86c1a","datavalue":{"value":"0785.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687919$59BD7823-83C6-40B2-9F8D-DE2E5E6CC875","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"347fecbfc47b37539faa04d7bda9825bc6c893ad","datavalue":{"value":{"entity-type":"item","numeric-id":198775,"id":"Q198775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687919$ACDC54E2-8BAD-4875-B14F-30BDFB005194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d19199dffc37186042cae11b138c9a5a1f4e279d","datavalue":{"value":{"entity-type":"item","numeric-id":186275,"id":"Q186275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687919$DCAACE23-7C84-4190-9311-0CFF66E7BB98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fcdad49ea46b13f97674cb7e1b0aa3145d1d287","datavalue":{"value":{"entity-type":"item","numeric-id":1625489,"id":"Q1625489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687919$11F11C01-261D-44C1-AEFD-015C5DFE76A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"45e1edb64efeee080173451c87c3f0c1d8534742","datavalue":{"value":{"entity-type":"item","numeric-id":174829,"id":"Q174829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687919$A061D174-145E-46EA-B79C-EC041BA77086","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"93627e26240e752cb19a924c1f02ee91d370ea3e","datavalue":{"value":{"time":"+1994-04-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q687919$A4395DCA-96E9-493D-9E20-4F69B18E8C36","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"060dee23b41b2d585b1d9137b520288901e8dd97","datavalue":{"value":"Let \\(c(G)\\) denote the circumference of a graph \\(G\\). The following notations are used in the statements of results that are announced in this letter:   \\(\\sigma_ 3(G)=\\min\\{\\sum^ 3_{i=1} d(v_ i): \\{v_ 1,v_ 2,v_ 3\\}\\) is an independent set in \\(G\\}\\),   \\(\\overline\\sigma_ 3(G)=\\min\\{\\sum^ 3_{i=1} d(v_ i)- |\\bigcap^ 3_{i=1} N(v_ i)|: \\{v_ 1,v_ 2,v_ 3\\}\\) is an independent set in \\(G\\}\\),   \\(\\rho_ 3(G)=\\min\\{|\\bigcup^ 3_{i=1} N(v_ i)|: \\{v_ 1,v_ 2,v_ 3\\}\\) is an independent set in \\(G\\}\\), and   \\(\\rho^*_ 3(G)=\\min\\{|\\bigcup^ 3_{i=1} N(v_ i)|: \\{v_ 1,v_ 2,v_ 3\\}\\) is an independent set in \\(G\\) with \\(\\bigcap^ 3_{i=1} N(v_ i)\\neq\\varnothing\\}\\).   Results: Let \\(G\\) be a 1-tough graph of order \\(n\\).   (a) If \\(\\sigma_ 3(G)\\geq n\\geq 3\\), then \\(c(G)\\geq\\min\\{n,2\\rho^*_ 3(G)+ 4\\}\\); consequently, \\(c(G)\\geq \\min\\{n,2\\rho_ 3(G)+ 4\\}\\).   (b) If \\(\\sigma_ 3(G)\\geq (3n-13)/2\\) for \\(n\\geq 15\\) and odd, or \\(\\sigma_ 3(G)\\geq (3n-16)/2\\) for \\(n\\geq 16\\) and even, or \\(\\sigma_ 3(G)\\geq n\\) where \\(n\\leq 14\\), then \\(G\\) is Hamiltonian.   (c) If \\(\\sigma_ 3(G)\\geq n\\geq 3\\) and \\(\\rho^*_ 3(G)\\geq (n-4)/2\\), then \\(G\\) is Hamiltonian.","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$BF158948-00C0-40C0-B311-FDF72993848B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687919$ED6CEF29-C06B-42A1-A673-3ECBD5AD1FB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687919$0A566B5C-C72E-4130-91BD-E67264857FE2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"206f4f85d6e2b42a93c8839de780edc195882b4b","datavalue":{"value":"436768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687919$D47074C7-0DC9-4B8F-9F5E-08097560CF17","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8d5f3b694f8f66eb4b53fd7e78857c6731e3b3b","datavalue":{"value":"long cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$B3336F6E-2829-4462-BA3B-319DF5F7D552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4c871027010aa29d312ffd2216be86897de61b","datavalue":{"value":"1-tough graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$130FAE07-9E49-41D4-97FB-9DBD4B8F74CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4b29eca207e72ea970aece64a227fbe94ab989","datavalue":{"value":"Hamiltonian graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$816B7D33-ADBC-4814-9892-DD8E89E3F872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24bb3b9099154c0f5a16d2b4a10fda71d3228c16","datavalue":{"value":"circumference","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$8320F1B4-0F54-4510-AB20-A5534D14BE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q687919$1733619E-6AB0-46A2-9EA1-B8BD1DB4D439","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8a2dfbca777895516fe0db0b03c60fbe8f44d123","datavalue":{"value":{"entity-type":"item","numeric-id":800380,"id":"Q800380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687919$07C97E03-0F94-4344-9FE4-860FDB83E537","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":"Q687919$0DF97EB3-E51E-4BDA-8839-F45641A6CC37","rank":"normal"}],"P1643":[{"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":"17c9a072be29c3ab96491cf5ae6a8a41a30167ab","datavalue":{"value":{"amount":"+0.9628306031227112","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":"Q687919$C6C3B2F6-282B-437A-80ED-0239C3F73A1E","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":"2f9760bf2beb2081bb871ba2b5050a52e8f91152","datavalue":{"value":{"amount":"+0.9374743700027466","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":"Q687919$613EA385-E8E8-4E62-8B36-0FAA71D295ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c90bb7513c9e5bf82be2cf8cbbd1bfa3b7140be2","datavalue":{"value":{"entity-type":"item","numeric-id":4852400,"id":"Q4852400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9504ec60181c0ddaa43a31a4549cd5093f0271b9","datavalue":{"value":{"amount":"+0.9373925924301147","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":"Q687919$C02A0F46-5CF1-44FF-847B-70E49CF65E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da74fc4968271d56affadeaa36b5d6ff7507ff6f","datavalue":{"value":{"entity-type":"item","numeric-id":2563428,"id":"Q2563428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a73178757aeb698b760642b8b4f1ea4032098231","datavalue":{"value":{"amount":"+0.934498131275177","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":"Q687919$A0E8F5EF-983A-42B3-8CED-1CB7D708F083","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":"864f8f336375dce68322d96d5e538f219245b7be","datavalue":{"value":{"amount":"+0.9107852578163148","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":"Q687919$23F4961D-96EE-4305-803D-4901791C0EB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Long cycles in 1-tough graphs with large degree sums","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Long_cycles_in_1-tough_graphs_with_large_degree_sums"}}}}}