{"entities":{"Q1916113":{"pageid":1926855,"ns":120,"title":"Item:Q1916113","lastrevid":69287745,"modified":"2026-04-13T06:00:27Z","type":"item","id":"Q1916113","labels":{"en":{"language":"en","value":"Toughness, hamiltonicity and split graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 896002"}},"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":"Q1916113$85189581-6DBA-4E29-B793-0EAAF9008546","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1ca870a35bbe5c1e747a197a10561deb944c4fee","datavalue":{"value":{"text":"Toughness, hamiltonicity and split graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1916113$0FDFF95A-3FD2-4992-B167-63EBD3C57FB3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ea17369bd537445d5c9844a04a8a264e68a376e","datavalue":{"value":"0855.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916113$145C829B-76D4-4793-9DFF-08559C6CC7DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35c9bfd655b60532a348de80529b1b3b1efaded8","datavalue":{"value":"10.1016/0012-365X(95)00190-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916113$CA851EE0-28FC-449C-869B-AA3CBE849650","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$6AAB7FEE-019B-4F39-97BD-D340AA79D9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d838f189c5dee0252f326bcac58fa27d9924b24e","datavalue":{"value":{"entity-type":"item","numeric-id":190507,"id":"Q190507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$47A44603-9A45-425B-B223-125508A12810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d40587e04768d5f70473e58fb8ddc324137351a9","datavalue":{"value":{"entity-type":"item","numeric-id":185069,"id":"Q185069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$30D110CD-9A86-4D48-B085-14E62C8F35F5","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":"Q1916113$10473829-5A9D-4E79-8AAA-921CCBD570DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10e532ff1bc6d13eb9c7e7cf3ee728d0229037bd","datavalue":{"value":{"time":"+1997-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1916113$B1A838FD-56CA-4FFD-B29A-F60C1279A950","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c580e8d85fe7b177a56bad11d4cadafbaf4ea2b","datavalue":{"value":"The toughness of a finite undirected graph introduced by Chv\u00e1tal plays an important role in connection with the hamiltonicity of a graph. For a non-complete graph \\(G\\) its toughness \\(t(G)\\) is defined as the minimum over all cutsets of the size of a cutset \\(S\\) divided by the number of connected components of the rest graph \\(G-S\\). A graph is \\(t\\)-tough if its toughness is at least \\(t\\).   The authors study further properties related to hamiltonicity, traceability and toughness concepts. They present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete. They show that every 3/2-tough split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to 3/2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916113$818E2A8E-1A3C-438D-80B9-DEC502D3DE61","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$C9664834-B22A-4E9E-8319-973E0A997E8D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916113$4B04B704-27B9-4A16-996F-C6AEBE95462F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916113$95FFAD17-C5EE-4A36-8B01-9AA422BB8AC4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"41c8db3efeaccd7b6a0cfbfe5e993947c0187495","datavalue":{"value":"896002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916113$2C7BA9D6-A2D6-49FC-BA50-B6D7617ED186","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09f50b21eea75ffdc199ef6f495164ba5c08bd0f","datavalue":{"value":"toughness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916113$AFB33640-B9DF-4171-ACB8-9793D909EDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad7f6c16e18413af432f8e820582fb2aa296646","datavalue":{"value":"hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916113$783B6DC0-7904-4237-9EEE-868119DC5C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916113$18948382-913B-4690-A939-23437CCEEB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8364c4db3fffd0a014142e381813cb4f26f28ac","datavalue":{"value":"split graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916113$812BF1C3-9153-41AF-990F-15A996ADDB67","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":"Q1916113$59B91115-C15C-4D4F-989D-039B75E2FFE1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$A8DC81B1-494E-476D-ADA4-CF067DCA82B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$C3B927E5-95BC-4B81-AE16-3F7207BD049D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"261b30465b2f9b97ed6391eb2fa761c1d658a808","datavalue":{"value":{"entity-type":"item","numeric-id":918697,"id":"Q918697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$8F7AB451-1DE3-4A0E-878D-DFD3EC943005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba317c2146f6a5c380b7bc49ee4595b399d87ef0","datavalue":{"value":{"entity-type":"item","numeric-id":4290577,"id":"Q4290577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$A29110CA-C18E-4390-B47B-A0600236CC29","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":"Q1916113$75E0DEB9-BA21-4333-8E8E-C3D6A57C8B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68bb4e6ce6c2a86a07604d83c24ef9b0f55717d0","datavalue":{"value":{"entity-type":"item","numeric-id":4871126,"id":"Q4871126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$D215DC2F-0C55-439B-98FE-5EF23F5CEA52","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":"Q1916113$09D3AEDB-1AA6-4975-9618-D5BA7CBE3FFD","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":"Q1916113$38AB0D6B-A896-499F-818E-EB0F0065F6F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92c907f08421493682920998b233ac32ae250a2a","datavalue":{"value":{"entity-type":"item","numeric-id":1198484,"id":"Q1198484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$59640325-ED52-4C3D-BF73-0A21987B18EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebc9cc4c410a6a417840c5dceb8507709e059781","datavalue":{"value":{"entity-type":"item","numeric-id":1363656,"id":"Q1363656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$45AAC1CD-0BE4-43F9-B5B6-1771B196B725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"405868d47a38f337608969d970fc6ab058e96a24","datavalue":{"value":{"entity-type":"item","numeric-id":4302282,"id":"Q4302282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$52CB178C-1C72-4D7F-9B29-B632CA6C5828","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":"Q1916113$92C6A948-A84E-453B-9A74-DDFA061B0707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$9DE62542-A302-45BF-B4AB-63C87CB72BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$4C6A93C7-E207-4433-A66C-9414AD392DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b37938f3cc091ba24b9864915f8f0f483daafbc","datavalue":{"value":{"entity-type":"item","numeric-id":2366022,"id":"Q2366022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$2865AB65-656E-4D62-87C4-6FE22AC25DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$14C3A4BD-3FF1-47B3-BA40-EC05D2B1F0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$FA0249A7-DE89-487C-A008-C37683CE55DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b276b586d736817671f4862a5f3d7d61c80c5167","datavalue":{"value":{"entity-type":"item","numeric-id":3795704,"id":"Q3795704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$BC5999FB-A71A-4D62-B2AC-1951C9CED2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fddf78676d43f688f22d0ab9603f5b22b0a030","datavalue":{"value":{"entity-type":"item","numeric-id":1066674,"id":"Q1066674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$2F7386C7-B18B-43C6-B465-AACDAB0C88A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$C69DEA89-21DD-444C-827F-28B9F3642AC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5819b916a40dd6679d6596ec0dc1aa2484ff3d","datavalue":{"value":{"entity-type":"item","numeric-id":915465,"id":"Q915465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$E3ACC584-77A9-4A0D-A269-906F3384E3B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21c43372301f70e76e60b904e2eaf69006c9ea3e","datavalue":{"value":{"entity-type":"item","numeric-id":3782804,"id":"Q3782804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$81871CE3-A738-4D25-844C-4A5EA23D9778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9a77b50c698d35e0bfbd498c866f480eb9f390","datavalue":{"value":{"entity-type":"item","numeric-id":5591387,"id":"Q5591387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$45AD29DB-0E1A-4B1E-BF9B-C58C3B934FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$216264BE-C7D8-48F1-B8CA-6580B3F20735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3fb5f043baeb68cce6e45f22256fe3a039c78a8","datavalue":{"value":{"entity-type":"item","numeric-id":5816402,"id":"Q5816402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916113$9CEECAB5-6F8C-48A1-9961-C1767A043A85","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f11bd6cd0b170d9450915c75cef01a67b341c1e2","datavalue":{"value":{"entity-type":"item","numeric-id":1584388,"id":"Q1584388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"140dce90b438cdc6ee9aeb1e78b3b23775a57bd4","datavalue":{"value":{"amount":"+0.8568321466445923","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":"Q1916113$092E2A91-4E7B-4DC6-BE29-802EF9D121B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71e2afe15e0c6ae24bcdd903fca855dee69e0103","datavalue":{"value":{"entity-type":"item","numeric-id":5417820,"id":"Q5417820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"497979cc1a8ba8037e1d0db61e9f19b71a0bbb4b","datavalue":{"value":{"amount":"+0.8436225056648254","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":"Q1916113$B5AECC11-79D1-4849-ADD6-B92B0A3E3F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0677912874cb788f9e98474d96be8355fb41c2d6","datavalue":{"value":{"entity-type":"item","numeric-id":1356703,"id":"Q1356703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd3f1720f383fb504bb680a2bf023d110eb52134","datavalue":{"value":{"amount":"+0.8286039233207703","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":"Q1916113$A0F1CC84-A514-471B-B1AF-4E2253012221","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Toughness, hamiltonicity and split graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Toughness,_hamiltonicity_and_split_graphs"}}}}}