{"entities":{"Q1952726":{"pageid":1963468,"ns":120,"title":"Item:Q1952726","lastrevid":57631605,"modified":"2026-03-31T16:53:00Z","type":"item","id":"Q1952726","labels":{"en":{"language":"en","value":"Disconnected forbidden subgraphs, toughness and Hamilton cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6169811"}},"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":"Q1952726$F0DE71C6-C1B8-412B-A79C-5A5EBB4B0CFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f62198181d025219b91b673acdda593d70b15cc","datavalue":{"value":{"text":"Disconnected forbidden subgraphs, toughness and Hamilton cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1952726$49539120-72E0-471C-8F4F-60ADCAABD992","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"408fb3b417df1fd8771ecc86921319c0d1ae7360","datavalue":{"value":"1264.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$D5CB964E-DBD4-4121-A07E-D1F4125D52E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfc1a95c95ca216e04e6d18d1b4e7c4e4371fc08","datavalue":{"value":"10.1155/2013/673971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$29BD4F5C-4703-437C-BA42-C26CBF138247","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b801fa26a6374c23f1702ac9d0e841f5c0baf41","datavalue":{"value":{"entity-type":"item","numeric-id":367096,"id":"Q367096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1952726$F561AEAE-4726-465C-A8F0-BB7BDD7094F0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6c22b0251193a12b642ef29ef728ba20c2b35c6b","datavalue":{"value":{"entity-type":"item","numeric-id":361576,"id":"Q361576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1952726$355218E0-2396-4264-B8CA-28CDCA0746C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a099eaf742a5e6ca6d360d203620e441cafc43b","datavalue":{"value":{"time":"+2013-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1952726$CC2B4EE3-766F-49D3-B723-0B9F6A9A8B1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f4d62da0163b2891fe8ed05eb0953c6955203a5","datavalue":{"value":"https://arxiv.org/abs/1207.5132","type":"string"},"datatype":"url"},"type":"statement","id":"Q1952726$0D91A3CE-65E3-40C0-81FD-27BA80C4FE9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6da5babf50c0a40a3b8e14ac66ba3c059e44a62d","datavalue":{"value":"Summary: In 1974, \\textit{S. Goodman} and \\textit{S. Hedetniemi} [J. Comb. Theory, Ser. B 16, 175--180 (1974; Zbl 0275.05126)] proved that every 2-connected \\((K_{1,3}, K_{1,3} + e)\\)-free graph is hamiltonian. This result gave rise many other conditions for Hamilton cycles concerning various pairs and triples of forbidden connected subgraphs under additional connectivity conditions. In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures.    In 1997, it was proved that a single forbidden connected subgraph \\(R\\) in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with \\(R = P_3\\).    In this paper we prove that a single forbidden subgraph \\(R\\) can create a non trivial class of hamiltonian graphs if \\(R\\) is disconnected: {\\parindent=6mm \\begin{itemize}\\item[(1)]every \\((K_1 \\cup P_2)\\)-free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs;  \\item[(2)]every 1-tough \\((K_1 \\cup P_3)\\)-free graph is hamiltonian.   \\end{itemize}} 1We conjecture that every 1-tough \\((K_1 \\cup P_4)\\)-free graph is hamiltonian and every 1-tough \\(P_4\\)-free graph is hamiltonian.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1952726$8E1F06DC-942F-496C-9D1B-11BA7BF1114E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$349B565E-88D9-4B47-9333-E4CD17EC94CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$A6450837-367F-4E66-8BB9-3F111E0CE51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$592B4B78-C8EF-4541-9071-5F23413F0334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$9224A19C-A258-4C36-AF42-AAB826879614","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31e2554e03647db0c6fcb84cc6a9457f5a7f5bea","datavalue":{"value":"6169811","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$4D4496E2-64C0-4C1B-B8D5-0A2137920D75","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1952726$8A97D86A-82F1-4AED-865C-29EDF525D2CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"862b3f9bd3562fb19afcb46cb40fc8fc3f64ed24","datavalue":{"value":"Hamiltonian cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1952726$95207095-60B4-4544-BF4B-0FD4D0BC3825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a93b841c584418cc6a008ad31ca702d1b941c8a","datavalue":{"value":"connectivity conditions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1952726$779E5A41-E44A-47A6-980C-55296A810002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eaf9adf52050c891a4374ead908f48e41c75f9b2","datavalue":{"value":"single forbidden connected subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1952726$D020E1B1-6B81-45B8-BE39-696EE3598063","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fb99c43b22351d3f9db1b208a135ac28ff49bd9e","datavalue":{"value":"Q58998267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$6318A728-6B3E-42D0-955A-B654E5ADBDFB","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":"Q1952726$C4E10F65-091B-4628-8E49-6B9E44E1AED1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a88a632159b576805fafe7f8cc62e70e0ba104e3","datavalue":{"value":"W2091268837","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1952726$34E295D8-DBC7-405C-816B-58077D9F5FC7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1952726$9DC7DA2D-0626-4EDD-B521-36D993FF7E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdeb9f72de4cb2be23bf9647635f88f8ca939818","datavalue":{"value":{"entity-type":"item","numeric-id":2265440,"id":"Q2265440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1952726$48334FD7-B915-42C9-9E8F-1BFCA4B331FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072e3bfe7ab4b00d00c8edecc86703e8254664dd","datavalue":{"value":{"entity-type":"item","numeric-id":1367026,"id":"Q1367026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1952726$36944F00-5A71-464C-A980-AC347DC9775F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea41cca792224dcbf42d2143ede7ea5ff3c99cc3","datavalue":{"value":{"entity-type":"item","numeric-id":2062680,"id":"Q2062680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91dcc8f545bfb3d35f5d3211ac1df54e43381b48","datavalue":{"value":{"amount":"+0.8765943646430969","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":"Q1952726$8AA676B5-A08E-49E3-A605-936C0A0B47BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54fbe05a6a06f855e8a9ff6a27b59874aecfc530","datavalue":{"value":{"entity-type":"item","numeric-id":2675842,"id":"Q2675842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"665be8e3c3fd66f08442a855b93b49923c09f4c0","datavalue":{"value":{"amount":"+0.8638609647750854","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":"Q1952726$E8321260-7C2C-4F67-BEC2-75BE1990E2AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f767ceaea68bcfac6b78f4d92d551891a699b769","datavalue":{"value":{"entity-type":"item","numeric-id":339484,"id":"Q339484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55ed3d81b629343bb172cee16b4b9beabf2ce6f6","datavalue":{"value":{"amount":"+0.8515952229499817","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":"Q1952726$AAF03E97-1A27-4F60-8335-01212786987D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdd752137726b86232ebe9190626f8269f3e20f4","datavalue":{"value":{"entity-type":"item","numeric-id":2978174,"id":"Q2978174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9b7cdddaa82899d0490d8aee0b28d3332cf201c","datavalue":{"value":{"amount":"+0.8469147682189941","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":"Q1952726$B8CBD121-B574-4D49-8808-D337A7BD7126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fa3b39bc3b5aec7c756d29116191f6e9ccf419a","datavalue":{"value":{"entity-type":"item","numeric-id":5311916,"id":"Q5311916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0af747d041cd5517ec7738a53e315e4d752ba16b","datavalue":{"value":{"amount":"+0.8433445692062378","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":"Q1952726$F63EC928-4829-4E83-82E8-8840E4408482","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1952726","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1952726"}}}}}