{"entities":{"Q547792":{"pageid":549559,"ns":120,"title":"Item:Q547792","lastrevid":62659674,"modified":"2026-04-11T07:35:27Z","type":"item","id":"Q547792","labels":{"en":{"language":"en","value":"Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5913190"}},"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":"Q547792$BDBD1D29-2B88-414F-86A5-2F46C8BF44C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"03a03937911248d100db5706103b662c78bb60ca","datavalue":{"value":{"text":"Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q547792$711A95EC-5430-488D-A5F1-E002FDA49958","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d5d247b9282089c6b9a1aa3055cea9cd62af185","datavalue":{"value":"1219.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$BC80FF0E-C05D-432B-BE2D-AF951C2B95E9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f882b74bf32f34e15d83ed334c2173fb9313dd1","datavalue":{"value":{"entity-type":"item","numeric-id":377801,"id":"Q377801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547792$76C9A61A-CC20-41BE-8DC6-9FDB58039CD9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q547792$D86FD83F-B18D-4FBA-BAD0-932E31F87A0F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f112f61a1bf8951421a1669c4dcd263b162b3092","datavalue":{"value":{"time":"+2011-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q547792$8B25021B-F563-483B-85E2-C6D12CC60A66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"96a606d8c64be82154aca2e3d8d8196aecb58ea6","datavalue":{"value":"https://eudml.org/doc/224902","type":"string"},"datatype":"url"},"type":"statement","id":"Q547792$3DB9F645-D03F-4E1B-900B-3C74610EACF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f42d3af6ccf80152b689fe98f3ef14c9a94fab9e","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p132.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q547792$50382EB8-AC40-442B-A0E0-31097E0163F2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"76ef6ab83bdd91a11298f7d6b00b51572f8f2013","datavalue":{"value":"Summary: We describe an algorithm which enumerates all Hamilton cycles of a given 3- regular \\(n\\)-vertex graph in time \\(O(1.276^n)\\), improving on Eppstein's previous bound. The resulting new upper bound of \\(O(1.276^n)\\) for the maximum number of Hamilton cycles in 3-regular \\(n\\)-vertex graphs gets close to the best known lower bound of \\(\\Omega (1.259^n)\\). Our method differs from Eppstein's in that he considers in each step a new graph and modifies it, while we fix (at the very beginning) one Hamilton cycle \\(C\\) and then proceed around \\(C\\), successively producing partial Hamilton cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$F76A0A22-B42A-4373-92CB-2E01AF6180F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$355D5E2D-20A6-4C49-B71B-C57EC1C99782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$83C39379-E456-4D01-9976-704C0E0EC096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$1B39CCF6-1B78-4381-A3D4-0124C6632E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$93A709A5-67A6-4D86-AE53-0F457E889BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$9F379262-CC9A-4C3A-9C20-55176C439549","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d4157aaf6871fce533763b8fae84a7982cf1cc8","datavalue":{"value":"5913190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$218DB21D-3031-4E23-90A6-A1DA9322B5B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$B2E47FF6-2335-4E78-B530-9309BE2AA32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a7d7b07e610e54985a4cecf1967a7a8f9976eb","datavalue":{"value":"maximum number","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$3DD96396-E679-4C27-A167-D7658DC5BBB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$4DB1AC5E-8D45-41BB-BAF6-B446A58BC2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5081923bdec68eebad30674dbf6b103598fe01cb","datavalue":{"value":"partial Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$514B07B2-984C-452F-A0C3-83E2F75777E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q547792$3AD8F949-A8D4-4EC2-BF53-1D6AA029D3F8","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":"Q547792$E01077AD-F52A-4DD5-BCE0-209C7457BB57","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"704ac69b863b41d1e7e9e3f061c1bc86d62c4648","datavalue":{"value":"bafkreignkbzz6rra7ekxgbne6s7dxcqr6iwsyowszkovijpmkmhea7g3cu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q547792$47648E8B-9D75-4E4F-A471-F91192B224D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0865ec8169d4f806bb01b9979cb6cb58bbaee6d","datavalue":{"value":{"entity-type":"item","numeric-id":5194650,"id":"Q5194650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f32987df90b92d6ce7dc87a303a830480ab6fd6","datavalue":{"value":{"amount":"+0.9322019815444946","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":"Q547792$B3D7F7CD-1078-47B5-902A-A36CE337969E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0833844f30660298704046c0c375c0259f2312e9","datavalue":{"value":{"entity-type":"item","numeric-id":638522,"id":"Q638522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"889bc8f3b748cdac047e65949ad494d876b24ac6","datavalue":{"value":{"amount":"+0.8895915150642395","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":"Q547792$59760048-12D6-4123-A5ED-F8ABF93E08A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"881e7c21c23913ee91045e48189ec6e0e66bd67c","datavalue":{"value":{"entity-type":"item","numeric-id":1208363,"id":"Q1208363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1247e8689c14866e984199c0ea27ff2c82134d2e","datavalue":{"value":{"amount":"+0.8875146508216858","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":"Q547792$CC1AD1C5-B621-4508-B6BF-9F1EA192BB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b211d42a87ed887b8ed5ad666b4ece48b3bd9b98","datavalue":{"value":{"entity-type":"item","numeric-id":4895803,"id":"Q4895803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75081270f4009535ab32a6af8507783c8abd0610","datavalue":{"value":{"amount":"+0.8374237418174744","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":"Q547792$4E806D6A-559A-42C2-A568-40789248D4B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b66da092879a252920b384a77dc3da41ef3435b","datavalue":{"value":{"entity-type":"item","numeric-id":463046,"id":"Q463046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"026a4451d84c9746e1868260a10e790372839ee4","datavalue":{"value":{"amount":"+0.8222729563713074","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":"Q547792$4948DB24-1809-487A-B8E9-B2BA55566AA5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Enumerating_all_Hamilton_cycles_and_bounding_the_number_of_Hamilton_cycles_in_3-regular_graphs"}}}}}