{"entities":{"Q2488717":{"pageid":2499460,"ns":120,"title":"Item:Q2488717","lastrevid":78863285,"modified":"2026-05-06T12:36:38Z","type":"item","id":"Q2488717","labels":{"en":{"language":"en","value":"On mutually independent Hamiltonian paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5022890"}},"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":"Q2488717$94C13A42-7FBA-4068-8A60-5CDD6ECA3AF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"76d6fe8120673be808b46a8046b0e7b1e7c5c803","datavalue":{"value":{"text":"On mutually independent Hamiltonian paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2488717$F4779F9B-BBD1-4980-A536-251C7CB7CBCF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6e479c946399eb91ff315d6e4cabe40c9505c0c","datavalue":{"value":"1092.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$E0DB2273-8692-463D-8D4E-ACD2B6D9C186","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"adb3bfb425e99b65b15bae5924b5a3b00e1c339b","datavalue":{"value":{"entity-type":"item","numeric-id":623178,"id":"Q623178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$3BF1992D-A195-461C-997F-AF73C1CBF0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afb01f577eb93a0452d3f23c8785a5f9f5a1e7fe","datavalue":{"value":{"entity-type":"item","numeric-id":194666,"id":"Q194666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$614CED28-981A-49FC-8EB4-BC023B8080A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a40828612253da113575223808e4135125fb14bb","datavalue":{"value":{"entity-type":"item","numeric-id":726340,"id":"Q726340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$7A4D991E-FCE5-4628-AC36-B1BA6B460876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e1fba9190d8c20dbfb3ec2f6a0cf7d74275ca00","datavalue":{"value":{"entity-type":"item","numeric-id":194667,"id":"Q194667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$47D5B574-EDBE-458C-8D55-B843C5014095","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"60e92c9f06012150d8158f8bfafc8319965c5fdc","datavalue":{"value":{"entity-type":"item","numeric-id":176247,"id":"Q176247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$903A07A0-31A8-42D3-BEB8-CD8C592163F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"429ffb1c17047ba832e3bf9b487b194157e504f8","datavalue":{"value":{"time":"+2006-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2488717$CF3D98DC-BB33-4540-B423-901E63CE2F79","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e43f33b26613464b9a7adbea7e33c58cd9df8126","datavalue":{"value":"Two Hamiltonian paths \\(P_1=\\langle v_1,v_2,\\dots,v_n\\rangle\\) and \\(P_2=\\langle u_1,u_2,\\dots,u_n\\rangle\\) of an \\(n\\)-vertex graph \\(G\\) are independent if \\(u_1=v_1\\), \\(u_n=v_n\\), and \\(u_i\\neq v_i\\) for \\(1<i<n\\). A set of Hamiltonian paths \\(P_1,P_2,\\dots,P_s\\) of \\(G\\) between two distinct vertices are mutually independent if any two distinct paths in the set are independent. Let \\(\\bar{e}\\) denote the number of edges of the complement of \\(G\\). Suppose that \\(G\\) is a graph with \\(\\bar{e}\\leq n-4\\), \\(n\\geq4\\).  The authors prove that there are at least \\(n-2-\\bar{e}\\) mutually independent Hamiltonian paths between any pair of distinct vertices of \\(G\\) except for \\(n=5\\) and \\(\\bar{e}=1\\). Moreover, if the degree sum of any two non-adjacent vertices in \\(G\\) is at least \\(n+2\\) then for any two distinct vertices \\(u\\) and \\(v\\) of \\(G\\) there are \\(\\deg(u)+\\deg(n)-n\\) mutually independent paths between \\(u\\) and \\(v\\) if \\(\\{u,v\\}\\in E(G)\\) and there are \\(\\deg(u)+\\deg(v)-n+2\\) mutually independent Hamiltonian paths between \\(u\\) and \\(v\\) otherwise.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488717$39819AE6-D717-47C2-8E51-B0A1B5DD4AE5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$7276BFB4-9BA7-4B65-8DF9-15975893475E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$865CF041-631F-4232-888A-BF8F30494BC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"944c2f41c19ed30c13a5d5dc64a933d48a951eed","datavalue":{"value":"5022890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$448E6922-BF96-4153-8FDE-DB006C35277F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0428a0c8c8ff82607cd89aeef99c039182c1851","datavalue":{"value":"Hamiltonian connected","type":"string"},"datatype":"string"},"type":"statement","id":"Q2488717$0CE60C78-42D7-416C-81A2-60600E9D2C7E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02baa8c7a177bdddffdd29a44a9d552f63adf459","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$7AF863A3-61EE-4449-84DA-5570015841B6","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":"Q2488717$C616CF8C-B13B-47F0-9D38-AC219D518D3C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4e26a34717b9edbbfa82007a7d903602e8b3481e","datavalue":{"value":"https://doi.org/10.1016/j.aml.2005.05.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q2488717$AFBA8BE9-CC08-41FF-B6BD-A0E10EB7BB58","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c84b5b1c7bf8ce8533fd8a01e05c8d2f7eab42f5","datavalue":{"value":"W1999251076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$7400EAEC-F9E3-48BA-97DA-3300ACE96D86","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":"Q2488717$81A1A5FF-E891-40E9-8A15-FE2E1E0C109D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fbb5ee59c3c5fba8b68dc26e64c473270f6227","datavalue":{"value":{"entity-type":"item","numeric-id":2545100,"id":"Q2545100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$E6A2EBF7-1F24-4C70-AFC2-E0BBFE5F12E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14dcc9c96f6c72fbc9a4feb8a83dc5eacad8748","datavalue":{"value":{"entity-type":"item","numeric-id":3265306,"id":"Q3265306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$66A59A55-5C0E-4CCE-A095-3CC9ACB55DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"855bd3e79b7474d336e4c328190bebd9b3b4b091","datavalue":{"value":{"entity-type":"item","numeric-id":5318273,"id":"Q5318273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$A8618B6C-99EF-4AC3-8198-15AB4F3DE22C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fda4b4f3f642da69f3574160a584d145f6434b0","datavalue":{"value":{"entity-type":"item","numeric-id":775674,"id":"Q775674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2488717$4036647F-1308-4E95-B63C-D9A9594FEE5C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c601f47afd07738e41be62a1f406d37485772d4f","datavalue":{"value":"10.1016/J.AML.2005.05.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2488717$66D93CEF-2030-4344-84CA-8B74A79722CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"573876b1b7dda12b0d5ac0704d0ece50e21b4b15","datavalue":{"value":{"entity-type":"item","numeric-id":4683325,"id":"Q4683325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ce246a226fbc57ae2e928d23a287d103f256810","datavalue":{"value":{"amount":"+0.8902360200881958","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":"Q2488717$F8A1314B-C15B-4B5E-836B-E742F3F9F7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7ec0bbe25f92a8e25f5691809556a4712e6c9c1","datavalue":{"value":{"entity-type":"item","numeric-id":1033035,"id":"Q1033035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7146fe90b7f61883ad84c710b9a492c779a957d1","datavalue":{"value":{"amount":"+0.8613681197166443","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":"Q2488717$C881B9E6-7C24-4C70-8988-580900FCC831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b732fcfdf98d29c11dc77d0ee4b37fd07cac5b10","datavalue":{"value":{"entity-type":"item","numeric-id":2846630,"id":"Q2846630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d64d5164a7b7ca5ca2eb2d78c6fc45a0d1abf48","datavalue":{"value":{"amount":"+0.8480598330497742","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":"Q2488717$AE2BBE3D-3250-4E6C-9B95-C3F91FA93853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c60b6f24705d30ee36f6a7e97ff56a9a0797e6","datavalue":{"value":{"entity-type":"item","numeric-id":659782,"id":"Q659782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"937cbc25f894f597ebe9186bbd70c04632d177a4","datavalue":{"value":{"amount":"+0.8246809840202332","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":"Q2488717$96262346-90F4-4CA6-9A0E-9F3410C6357A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89cd3233bf2ac372d3a21c8206c644b29932da8f","datavalue":{"value":{"entity-type":"item","numeric-id":5318273,"id":"Q5318273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7249744925a9c02ea407471f85a776907f62b7e","datavalue":{"value":{"amount":"+0.8130322098731995","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":"Q2488717$500E18A3-35EA-401F-9D71-87CDD165EAA5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On mutually independent Hamiltonian paths","badges":[]}}}}}