{"entities":{"Q1813740":{"pageid":1824482,"ns":120,"title":"Item:Q1813740","lastrevid":69027108,"modified":"2026-04-13T03:49:12Z","type":"item","id":"Q1813740","labels":{"en":{"language":"en","value":"Toughness of graphs and the existence of factors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4915"}},"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":"Q1813740$413C6229-04AE-4C71-9857-0C2751B7495B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"082cee76347a7c8a62a79ba0a5cb518d011aa6de","datavalue":{"value":{"text":"Toughness of graphs and the existence of factors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1813740$2C084389-6B93-472E-BF09-8E9D3121B893","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9398536a7b8886259205d58c47c559787b21c86a","datavalue":{"value":"0739.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$2FE1F299-C8CB-4427-8161-AB2A750AF356","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d21c013229262656f48f64cba6a5a14c0beeb60","datavalue":{"value":"10.1016/0012-365X(90)90297-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$73339196-C4A9-47A2-A7E3-32E76A24F1CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bc38e12447b15e4ab4a8c35933e3caedc893193","datavalue":{"value":{"entity-type":"item","numeric-id":621381,"id":"Q621381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813740$5033098D-55ED-432F-BC8B-22AD0F02405F","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":"Q1813740$C1EBE47D-6AEA-4EE4-8758-714E6478A43B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1813740$A43D5D7C-2EF8-4F24-9EB1-42B3E8612171","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd22ce36dc9a5f2bbecd890fc6810b293927577c","datavalue":{"value":"The toughness \\(t(G)\\) of a graph \\(G\\) is the largest real number \\(t\\) such that the deletion of any \\(s\\) vertices from \\(G\\) results in a graph which is either connected or else has at most \\(s/t\\) components. This concept was introduced by Chv\u00e1tal, who conjectured that if \\(G\\) is a graph, \\(k\\) is a positive integer such that \\(k| V(G)|\\) is even and \\(t(G)\\geq k\\), then \\(G\\) has a \\(k\\)-factor.   This conjecture was subsequently proved by \\textit{H. Enomoto, B. Jackson, A. Saito} and the author [``Toughness and the existence of \\(k\\)-factors'', J. Graph Theory 9, 87-95 (1985; Zbl 0598.05054)]. The paper under review derives two new theorems, both of which contain Chv\u00e1tal's conjecture as a special case. The more easily stated of these is the following.   Let \\(G\\) be a graph and let \\(a\\) and \\(b\\) be positive integers with \\(a\\leq b\\). If \\(a=b\\) assume that \\(a| V(G)|\\) is even. Then \\(G\\) has an \\([a,b]\\)-factor if \\(t(G)\\geq a-1+{a\\over b}\\). An \\([a,b]\\)-factor is a spanning subgraph such that each vertex has degree \\(a\\) or \\(b\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813740$F6557FAF-57D8-4758-94B9-95FC7BEB0E3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$03623DA4-F6FA-4B31-AD76-A0202D9CEB13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$3CF4EB9D-8B93-4618-8FA3-F4C85BA1F9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$57EA8DA8-A5EA-4942-9D15-E476F43834BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a93eea0d2363b99419b28a1364a65635ea70139","datavalue":{"value":"4915","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$12DFD7D2-B644-4503-A474-6BABCFDE3B13","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09f50b21eea75ffdc199ef6f495164ba5c08bd0f","datavalue":{"value":"toughness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813740$E1AED0CB-ED31-4E2F-B057-7B03CBC1C996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ad43e1b751ec63152983833267b91de74c4013","datavalue":{"value":"\\(k\\)-factors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1813740$4C6127B9-065A-4126-95A5-CAEEB7A2A952","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":"Q1813740$9A69500E-C5A5-4554-AD6E-80D90D5A51D9","rank":"normal"}],"P223":[{"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":"Q1813740$1FA5662E-428D-439A-AE7F-E62CAE2CF74E","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":"Q1813740$A103D6E0-2785-4368-8240-7FE748CAB793","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":"Q1813740$BFF57402-C2D8-4B25-8E88-3A36CE9E5F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c00bceff6f60fb60810dddb1bd6a2b2ff394b899","datavalue":{"value":{"entity-type":"item","numeric-id":5595084,"id":"Q5595084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1813740$7E0D850D-0B8F-4FF3-B10B-31834F820AC2","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":"Q1813740$F7B864C9-40ED-4854-B552-0C3FE1AF155E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"4c117f7c200a296e97a83ba59690e8ba19999981","datavalue":{"value":"Q127109471","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1813740$723A8AE9-648B-4F89-8771-292DC8AEDCB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0be819fba3ca9e8211ec6c4c9a43802ddb66ec03","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"313823fa93224f0187629654f3df27cf97dda406","datavalue":{"value":{"amount":"+0.9202322959899902","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":"Q1813740$1251CC0E-E146-401D-9B66-2AB4916B245F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"796d9dd59ff999abff8bf9b6a1dfa15b7ff1b68f","datavalue":{"value":{"entity-type":"item","numeric-id":4024344,"id":"Q4024344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6517a9510ad1e40d993a55b915d5e762b0ae4353","datavalue":{"value":{"amount":"+0.9183559417724608","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":"Q1813740$09DF8106-1D74-41D5-BA22-2DD676BC0B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"879bf054196e263af180f94df029b01a50613356","datavalue":{"value":{"entity-type":"item","numeric-id":4032983,"id":"Q4032983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4a01daf4764f858f68083b5b009387d112cb52c","datavalue":{"value":{"amount":"+0.902922511100769","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":"Q1813740$1B8B9070-E010-4CBA-9C54-657D1A15AAD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Toughness of graphs and the existence of factors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Toughness_of_graphs_and_the_existence_of_factors"}}}}}