{"entities":{"Q749553":{"pageid":751402,"ns":120,"title":"Item:Q749553","lastrevid":64131183,"modified":"2026-04-11T17:50:57Z","type":"item","id":"Q749553","labels":{"en":{"language":"en","value":"Long cycles in graphs with large degree sums"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4173015"}},"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":"Q749553$05B1AFD2-9C06-422E-A26F-73244D878BA0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fde4f3e950bb273cc1c5c23ec7ac6db39bc64590","datavalue":{"value":{"text":"Long cycles in graphs with large degree sums","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q749553$D6D250B2-2A98-412A-980E-FB03639ABCC8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e90391bef1253e86e5fe3526426a938af4a6d5b4","datavalue":{"value":"0713.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$9CBF06EB-1D0C-439E-AD95-405C5D978FBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e66ad3fdfc640f340fa0f00b90482d67f55399d","datavalue":{"value":"10.1016/0012-365X(90)90055-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$2BF6D219-8AB0-4A2A-ADF5-811637254FC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60ae56b79890118017fdfa61d163ccabbb05d00b","datavalue":{"value":{"entity-type":"item","numeric-id":585220,"id":"Q585220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$44377256-55C5-4C59-B940-AAC8A820368A","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":"Q749553$BFD988FA-2525-41B3-8FA4-DECC2F537E7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"73fb56bb2c6799cbe2d549466466c1fb6f1233b8","datavalue":{"value":{"entity-type":"item","numeric-id":918990,"id":"Q918990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$60E37359-3140-4268-9125-A7AB87736862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41fca74e9950a16c663ca86f884e7b8febbc1dc4","datavalue":{"value":{"entity-type":"item","numeric-id":290246,"id":"Q290246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$84E1559F-CED7-4B2C-9F15-49EBE052B2A0","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":"Q749553$F75CD12A-1899-4AE9-AB03-539A5E917D12","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q749553$4EABC39E-667D-42DD-A6AF-E10BB757CD1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fea4c9b97b6927485298058c3ac3b9062671a90f","datavalue":{"value":"Let G be an undirected graph on n vertices with no loops or multiple edges. The number of components of G and the independence number of G are denoted by \\(\\omega\\) (G) and \\(\\alpha\\) (G), respectively. G is t-tough if \\(| S| \\geq t\\omega (G-s)\\) for any subset S of V(G) with \\(\\omega (G-S)>1\\). A cycle C of G is a dominating cycle if every edge of G has at least one of its vertices on C. Let \\(d(x)+d(y)+d(z)\\geq s\\) for all triples of independent vertices x, y and z of G. The authors prove a number of results concerning long cycles in graphs with large degree sums. In particular, if c denotes the length of the longest cycle in G they prove:    1. If G is 1-tough and \\(s\\geq n\\), then every longest cycle in G is a dominating cycle and  \\[  c\\geq \\min \\{n,n+\\frac{1}{3}s-\\alpha \\}\\geq \\frac{1}{6}n.  \\]  2. If G is 2-connected and \\(s\\geq n+2\\), then  \\[  c\\geq \\min \\{n,n+\\frac{1}{3}s-\\alpha \\}. \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q749553$977280F6-1A8A-4899-9843-E5AF203F80E0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5a8b5716bc29dee4849a02abb2efc7b4cabc4b7","datavalue":{"value":{"entity-type":"item","numeric-id":328466,"id":"Q328466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$29962C0E-6054-42AD-ABE2-1A74D461174D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$60D3A973-44D9-4231-9E71-B1B78A1D1583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$D65208E7-B8C5-46EC-AF24-5C09FD511695","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d9dec65d76868fafee0a441d613e8165d8427919","datavalue":{"value":"4173015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$D15528F3-7682-4806-99BB-0C977C26AAD0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q749553$7670DF92-5269-4136-BC0E-A2EFFB9F4C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd1b93aedce11639d0bf358d04adbcf7e30406e8","datavalue":{"value":"t-tough","type":"string"},"datatype":"string"},"type":"statement","id":"Q749553$8D5E47C4-C6C1-4672-AFA4-2E62B790D9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c975ab5bc8d729ed0ef9c8d859287541463d71c1","datavalue":{"value":"dominating cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q749553$F8BB9014-D5F6-4504-A925-4206F8A701AC","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":"Q749553$742F8872-5553-4D8E-82FA-D191DD1B681D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8baf445319d2754ed1e8283ed9e6678265a85f99","datavalue":{"value":{"entity-type":"item","numeric-id":3731630,"id":"Q3731630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$234F1D7C-8106-4E91-B381-040053C2C532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cafb5f6af492e03b07ce207c5eeada71c475130c","datavalue":{"value":{"entity-type":"item","numeric-id":918991,"id":"Q918991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$3BE77764-0C77-44B9-A632-68C0E24658D7","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":"Q749553$A55250C5-1141-4706-8A0C-5E70E80FD5A0","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":"Q749553$00603CB1-D59F-471A-BFE1-5A3758870E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b041c2de3cb0899b21b87dfbe8b30290e5aaf6","datavalue":{"value":{"entity-type":"item","numeric-id":3820627,"id":"Q3820627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$04966D82-4035-4964-B373-AA28583719F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$65945C3E-94DA-4ABD-B2AA-2ED1D427A493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755f5e404bab61a83556c03ea51b1484066fd89c","datavalue":{"value":{"entity-type":"item","numeric-id":1253262,"id":"Q1253262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$8782D203-F154-4AA4-ADE0-30765DB034C5","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":"Q749553$28AC56D2-FCB4-449A-A340-539654EADEED","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":"Q749553$E89C751F-062C-4D38-A4DE-9FD19DC3CE81","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":"Q749553$C821BE5F-4253-4B9B-B175-FBA52CDFB79C","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":"Q749553$8CFDBCC9-B7EC-4271-B452-CD6637F160FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28f52a20998fad5a47cafacdd49c00f8d9d03466","datavalue":{"value":{"entity-type":"item","numeric-id":3699724,"id":"Q3699724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$65259262-E415-42A2-B967-A76B313F29BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b803ec79449ff5f537bf509ede2f4490481e2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1173098,"id":"Q1173098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q749553$A373EE91-50CA-4A81-A336-E503D372C0CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"79f3da723e4a6cd93ddaba83db8261f9551c3bf2","datavalue":{"value":"https://doi.org/10.1016/0012-365x(90)90055-m","type":"string"},"datatype":"url"},"type":"statement","id":"Q749553$9D30624A-1211-4BE9-97EA-C62CDD578507","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f6c7859732d4871d94febba8722db1091d260d3e","datavalue":{"value":"W2019698871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q749553$31EB9570-3A66-4900-A065-E9FC5196415E","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":"2c80b76a564900be88c6b36528da4e6875cfe6ce","datavalue":{"value":{"amount":"+0.8964793086051941","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":"Q749553$698EB935-C3AE-4FDC-80AC-2081C568F72C","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":"39c4f75f46da34f3c5241cd8c059e8d162128d41","datavalue":{"value":{"amount":"+0.8938284516334534","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":"Q749553$C06BA16B-0DF6-4F98-B0B1-08606302A146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06ce23982f48231b4b3bb8ff602525705fb66c4c","datavalue":{"value":{"entity-type":"item","numeric-id":4359587,"id":"Q4359587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"001f9311f9c3ff1fa85b6eeb613ba517f9b1c86d","datavalue":{"value":{"amount":"+0.8930803537368774","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":"Q749553$5D624E9C-0DAD-4BB7-804B-111323E4A6AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69791e564765a38eac6afbe8893abb4b118427b9","datavalue":{"value":{"entity-type":"item","numeric-id":1309446,"id":"Q1309446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b85f95e3d71bafc68df372d8d80682efdc0729e","datavalue":{"value":{"amount":"+0.89275062084198","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":"Q749553$81CAA403-0F99-440B-BFCC-967BF19726C7","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":"a2e90640dfbbf7be47746c5c0cb850234339bcc3","datavalue":{"value":{"amount":"+0.8887771368026733","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":"Q749553$9BE88249-A3DB-475F-82C2-34F08A7289C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Long cycles in graphs with large degree sums","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Long_cycles_in_graphs_with_large_degree_sums"}}}}}