{"entities":{"Q2643317":{"pageid":2654060,"ns":120,"title":"Item:Q2643317","lastrevid":79431065,"modified":"2026-05-06T13:53:31Z","type":"item","id":"Q2643317","labels":{"en":{"language":"en","value":"The neighborhood union of independent sets and hamiltonicity of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5182386"}},"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":"Q2643317$E3DBE831-5EBE-47C2-9006-DD4661F5EC69","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9091ec088a1d307f8c766f16f6ff2a20e001002","datavalue":{"value":{"text":"The neighborhood union of independent sets and hamiltonicity of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2643317$F3D37942-A1BE-4344-83CB-FD19CA048CC0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3fcc9d5a04ec3c52772591b13541fb47307bb06a","datavalue":{"value":"1137.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643317$16E56944-D42B-4C8A-8E15-107123D200E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46d700d519b963a9ea7e4e688485dc78f4f98f77","datavalue":{"value":{"entity-type":"item","numeric-id":1936365,"id":"Q1936365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$779CF56F-58B6-45EF-B655-41A09E86E941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4b11a42f00b16e73b84157136bc9ab0b1f01563","datavalue":{"value":{"entity-type":"item","numeric-id":2643316,"id":"Q2643316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$4E0B4DA6-556C-4CEF-9287-61572246E585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ade01a5cc81905ed299eab91798cb7d98b897d7a","datavalue":{"value":{"entity-type":"item","numeric-id":222615,"id":"Q222615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$29AFC8AC-99A3-4C1A-9FFD-5E0BF9923EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6084a52b9c34539817466666929e9d5234f184ee","datavalue":{"value":{"entity-type":"item","numeric-id":1169474,"id":"Q1169474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$4B787362-8950-41D3-A9A3-D87A4A5A0818","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":"Q2643317$2B75504C-8120-48BD-B8E4-1715B0DDABFB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"226fad3e536b676c763bdce84a93ee9c766c4ae5","datavalue":{"value":{"time":"+2007-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2643317$F2D5F3DE-0255-4821-B7AD-3BEB441E1523","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"47d2379ccccef9770562f201c643864b34be868b","datavalue":{"value":"Two classic sufficient degree conditions for Hamiltonian graphs obtained by Dirac and Ore are:  Theorem 1. (Dirac). Let \\(G\\) be a graph of order \\(n\\geq 3\\). If \\(\\delta(G)\\geq n/2\\) then \\(G\\) is Hamiltonian.  Theorem 2. (Ore) Let \\(G\\) be a graph of order \\(n\\geq 3\\). If \\(\\deg(u)+ \\deg(v)\\geq n\\) for every pair \\(u\\), \\(v\\) of nonadjacent vertices of \\(G\\) then \\(G\\) is Hamiltonian.  A natural generalization of the above results is to replace the degree of each vertex by the degree of a set of vertices. Let \\(G\\) be a graph with vertex set \\(V(G)\\). For each vertex \\(u\\) in \\(G\\), let \\(N(u)\\) be the neighborhood of \\(u\\). For \\(U\\subseteq V(G)\\), let \\(N(U)=\\bigcup N(u)\\), where \\(u\\in U\\).  The authors prove the following theorem.  Theorem 3. For any two positive integers \\(s\\) and \\(t\\), there exists a positive integer \\(N(s, t)\\) such that every \\((s+t)\\)-connected graph \\(G\\) of order \\(n\\geq N(s, t)\\) is Hamiltonian if \\(|N(S)|+ |N(T)|\\geq n\\) for every two disjoint independent sets \\(S\\), \\(T\\) with \\(|S|= s\\) and \\(|T|= t\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643317$D44B4962-5FB1-45D8-9815-5413DF2D90B1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643317$076AC16E-6F8B-415A-95E1-13B338F76259","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f88d1a0918c3164a604db42f3c664e5acde8b7e","datavalue":{"value":"5182386","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643317$BB801F9E-3621-4B34-9617-F82447918610","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c822c54638e4070b56aee42666fe01efcdddece8","datavalue":{"value":"Hamiltonian","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643317$7F74574B-F860-4F41-9C38-F35621E0C8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5a2e192f00d1793537ffea90620ae427779fac8","datavalue":{"value":"vertex insertion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643317$7B10C857-9173-464F-8AFA-C8446D5450E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0fd7794b25e208d094cde5658e2ceac5bb127a","datavalue":{"value":"the neighborhood union","type":"string"},"datatype":"string"},"type":"statement","id":"Q2643317$E4167315-C98A-4B6C-A86F-42AF5AE6934A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c373609087678f84cf49ac586680a31002124e72","datavalue":{"value":{"entity-type":"item","numeric-id":267204,"id":"Q267204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$53160E1B-9A31-4060-AD73-97BDF6E06C55","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":"Q2643317$8CF44064-12EE-4EC8-BB49-4AD4B2F5EA2D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f81a28c596dc9328f1cdd862cda7b3efc50d1116","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.10.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q2643317$3A0D6E51-1CEE-4CF7-9FDE-A694D20F19A0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1e47aeddad7df3fabd4d5415d76925fefbbc1036","datavalue":{"value":"W2011379998","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643317$BC665EFE-283B-4A3D-A248-22EEF49FB107","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ebf2ff7289a60b0ddf0a065925892eb0dfe2a8c","datavalue":{"value":{"entity-type":"item","numeric-id":1896341,"id":"Q1896341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$77BB31BD-FD77-4D9B-8BC5-D783105BAD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40095582840dd00857bc4c827d196e293cec6c5d","datavalue":{"value":{"entity-type":"item","numeric-id":4852399,"id":"Q4852399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$468E9F35-6A96-40FE-A2BD-302FE1016519","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":"Q2643317$37B055B5-3C28-4D3D-BBB1-9DC5A9C551DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c678a4d607ee7c59493765993ec168741685091b","datavalue":{"value":{"entity-type":"item","numeric-id":1313847,"id":"Q1313847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$6F7D68C3-5AB2-4F4A-801F-813E670E3584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af30aaaccaf9d27b80812e6b3e7b284bf93b0008","datavalue":{"value":{"entity-type":"item","numeric-id":4940054,"id":"Q4940054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$18CF0AD7-47DD-4655-866C-2AEB4EE71CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"419eb88874f1ce3b6e771bfee75ae0f7cf46a3f0","datavalue":{"value":{"entity-type":"item","numeric-id":3419703,"id":"Q3419703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$80536E45-56BE-42F4-BC71-94E063B7D281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ee4b5aec7c57f1369b27ad508e8d6185d4489d","datavalue":{"value":{"entity-type":"item","numeric-id":2551113,"id":"Q2551113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$B3F42F66-0B02-4B82-9EDA-4478963650C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$AFE2A21D-E71D-4385-878A-F202FBB2FF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b2e9c19a9b13a1e5db1e4c80b47b45380486c1e","datavalue":{"value":{"entity-type":"item","numeric-id":3981351,"id":"Q3981351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$242012BE-FD3D-4E1E-A407-D5BA9E46CFE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"561c7ce8c27e20759a236fb466d62fec73eb38f5","datavalue":{"value":{"entity-type":"item","numeric-id":1123212,"id":"Q1123212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$371CBFD6-593F-4E33-9DDF-739C9F69B9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09a099288c5b4d2b97b6515cac472b188350992d","datavalue":{"value":{"entity-type":"item","numeric-id":3744190,"id":"Q3744190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$128B1B7B-5040-497A-BF9E-52E7BA3EB15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6552cc85a61490eb3f50fd663ed958a48555f4a3","datavalue":{"value":{"entity-type":"item","numeric-id":3980626,"id":"Q3980626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$04D17639-0A8A-4822-91FF-146A5B38C30A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0d9c586ef9cf53af881c9950417cc5b66679aa","datavalue":{"value":{"entity-type":"item","numeric-id":3264678,"id":"Q3264678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$0F2ADA42-E8B1-4788-93FE-2AAB02E9AEC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fed399b92abfc52a389dd0d5dbc33dbca52005b0","datavalue":{"value":{"entity-type":"item","numeric-id":3783321,"id":"Q3783321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2643317$400C4753-9BBE-45A0-9A02-1F88E9DF0FB7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d597113f05f93b951d00a91a1345b1d8b5b304b8","datavalue":{"value":"10.1016/J.DISC.2006.10.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2643317$DC453122-CD9F-4731-8A70-88167577B050","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc3a5edb91602e4251bf0056f25d73287b92c2b1","datavalue":{"value":{"entity-type":"item","numeric-id":3419703,"id":"Q3419703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3c6dbf6ce9f91bdde4d048e7c80dac25a1f3b78","datavalue":{"value":{"amount":"+0.8948147296905518","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":"Q2643317$DF6A9B2C-C4AC-4E9E-BC01-C415CC312205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db1129380d5758380cfdc3c7e9ddb6c6d22d2be6","datavalue":{"value":{"entity-type":"item","numeric-id":4940054,"id":"Q4940054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bd4da82ae5c5b197f4f71877272c1a477a7e86d","datavalue":{"value":{"amount":"+0.8897295594215393","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":"Q2643317$CB82FC09-7917-4E45-A4D7-67594901601F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"086661f08c3677e2075719c51098ba4a12d09f3c","datavalue":{"value":{"entity-type":"item","numeric-id":4025576,"id":"Q4025576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51c4f10b7ee5d861e1010cfa93b529472bae092a","datavalue":{"value":{"amount":"+0.8889850378036499","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":"Q2643317$52B53068-478A-4E13-846D-B306E6B6EF56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b5c565915551889f678e5d1ff3a8911dfb0f00","datavalue":{"value":{"entity-type":"item","numeric-id":1336717,"id":"Q1336717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dcd776fb5125480e3a2515fdc07a9c01d198498","datavalue":{"value":{"amount":"+0.8854631781578064","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":"Q2643317$D762D98E-284A-421D-8528-C5A77C320F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3345f6485767f33e5a50bc4fa6e84aaecb25d91","datavalue":{"value":{"entity-type":"item","numeric-id":1199474,"id":"Q1199474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3770928208760990f9af97d7ef1d500624987285","datavalue":{"value":{"amount":"+0.8805197477340698","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":"Q2643317$648411F0-44BD-461C-9391-082D1B9101CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The neighborhood union of independent sets and hamiltonicity of graphs","badges":[]}}}}}