{"entities":{"Q2714402":{"pageid":2725141,"ns":120,"title":"Item:Q2714402","lastrevid":79276541,"modified":"2026-05-06T13:33:06Z","type":"item","id":"Q2714402","labels":{"en":{"language":"en","value":"Pseudo-hamiltonian graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1604328"}},"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":"Q2714402$E468DE4D-55C7-4506-A0B6-7896D4F4B481","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4799cecef74f094f4a273c0aad8c826220b2d417","datavalue":{"value":"0973.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2714402$79C529B9-5692-4A48-8D42-FFFA881BDD3A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"206b3ec8cbaf149080c58314ec18c3b633966649","datavalue":{"value":{"entity-type":"item","numeric-id":190504,"id":"Q190504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2714402$74DE52D6-4061-454E-AAB5-34DC4C58C24E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2714402$1310B300-D8D5-4E26-8F04-060EA8ECC672","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24a558bf24d5f00d94b5bae7f77cc1862c3e2d13","datavalue":{"value":{"time":"+2001-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2714402$2EB689AB-BE8E-4BC7-BBB7-79B7338C4D4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2714402$328A84F3-1833-42F1-A926-AAD9029B48B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2714402$0CE1604B-4DF8-4E2B-8BA1-26B89EB95495","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a1e9e26e217fd0cb4b4dbdfe71236f60994996e","datavalue":{"value":"1604328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2714402$96E9FF65-1748-434F-8EA0-26830440590F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa1d6b57bc157c141e0a31e860215a1b7eb88b19","datavalue":{"value":"pseudo-hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$6416F15F-84A5-447A-BCCC-537C4131DD21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68acc0dd269d54a3f775de29cee0ae7e86985539","datavalue":{"value":"pseudo-\\(h\\)-hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$65CD94BA-7FF1-4FD3-84BD-123574010E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3eb6fbe21ec2743767ecc611b33ca85eaa413e5a","datavalue":{"value":"regularizable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$64C6175E-3405-46BF-8E33-34EC4860FE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$54E2490F-04A8-4437-9CFE-AE09CD417DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8364c4db3fffd0a014142e381813cb4f26f28ac","datavalue":{"value":"split graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$090F88F2-D9E1-4352-8A47-BB6FA8E8A1E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$E4B57058-8DE0-4B7D-968A-D63F351A41F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81693dbc4c95cc79b419a6d43d2fbc473c04ab32","datavalue":{"value":"cocomparability graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$2AE1AFDF-C2AC-48EF-80E1-C4155F2DF078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$3E6E15DF-B634-487F-872A-EA5B3EADDD64","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":"Q2714402$B2DFD763-E22F-47AB-A41D-EF64BFA79EF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c62ee7984b9c0eb6747a4c433c56e309b0263ed0","datavalue":{"value":{"entity-type":"item","numeric-id":4373668,"id":"Q4373668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$C8891604-5F7D-4DC0-828D-A37C08763108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a43f7fdf62d02e2ae48894c0f54a1be6dc127260","datavalue":{"value":{"entity-type":"item","numeric-id":1971217,"id":"Q1971217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4319f3785bc9309aed8b2404eccccd22db0d7864","datavalue":{"value":{"amount":"+0.9807664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$17CA431D-932C-48C7-9C38-10424612C4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31b22c2b387ad4c1320707d6c1f84f192384efa0","datavalue":{"value":{"entity-type":"item","numeric-id":4724664,"id":"Q4724664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3074d5ea541e6272fed29747b6248a11e1280f5","datavalue":{"value":{"amount":"+0.9237491","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$E64A8583-BF72-40F2-8F5E-71B5D39B1272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa1491d4f766f61cdcf25bd6e69dab498944f931","datavalue":{"value":{"entity-type":"item","numeric-id":3356326,"id":"Q3356326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00bd644313d85c6dfbfcd222aa80a082822202f4","datavalue":{"value":{"amount":"+0.9228284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$8F1ECC13-07DD-4719-AE1C-B580FBB31E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86c968f08e97d63d3cc05fabf1b266bbc372d393","datavalue":{"value":{"entity-type":"item","numeric-id":4418085,"id":"Q4418085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329b5a88570830a8d8ec4be2bc990d4ee25b6ecb","datavalue":{"value":{"amount":"+0.91547114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$B69FDA5D-8DFC-419C-8591-090E66D20108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9c4631252effd187f3ae27824fc6b3297fb95f5","datavalue":{"value":{"entity-type":"item","numeric-id":945175,"id":"Q945175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36c3fb9d7509e583b89d78bfb84c3d2c5380d20c","datavalue":{"value":{"amount":"+0.91478753","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$380139B0-3476-4F37-8FD1-E9EC8E06515D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d761539b7097032e322d6a974825ddce2cb212bf","datavalue":{"value":{"entity-type":"item","numeric-id":912871,"id":"Q912871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15a4483b953663238202fbe8e5f8236e3667487a","datavalue":{"value":{"amount":"+0.9079561","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$D73DF632-28AE-47BD-ADD6-B785A77B0D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5519d5e6d8e1cf6a8cc3a756b7b4d968c7a47b6","datavalue":{"value":{"entity-type":"item","numeric-id":1084416,"id":"Q1084416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65b4147e5f588ce6b36fba869d0041840e2b4175","datavalue":{"value":{"amount":"+0.9068042","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$CB721F6B-B407-4013-AD61-AED7A9E1989B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"305655d7edde1f57b48f7986874dd1cd40354ee6","datavalue":{"value":{"entity-type":"item","numeric-id":803159,"id":"Q803159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65a7b432a79ee191c3bf926eda22a1c3d1cd5d98","datavalue":{"value":{"amount":"+0.90262735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2714402$9FD6751E-B89D-452D-BF68-A52DF6DEF0B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8deb7d6688d6f74ec1edad50aa304abb9567d7e","datavalue":{"value":{"text":"Pseudo-hamiltonian graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2714402$10E7ADC8-A0BA-42CC-AFD6-B557BF10A9A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a48ab4f78ae1700d4809c5ff5f0191168fe3ff96","datavalue":{"value":{"entity-type":"item","numeric-id":2803044,"id":"Q2803044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2714402$A105C466-A547-406A-ADCB-8BD94DF10C90","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b11f4cb6bbe4d17c73adba27c1064f1311cd605","datavalue":{"value":"In this paper a pseudo-\\(h\\)-hamiltonian cycle in a graph is defined as a closed walk that visits every vertex exactly \\(h\\) times. The pseudo-hamiltonicity number ph(\\(G\\)) of the graph \\(G\\), is the smallest integer \\(h\\geq 1\\) for which \\(G\\) is pseudo-\\(h\\)-hamiltonian; in case no such \\(h\\) exists, ph(\\(G\\))=\\(\\infty \\). It is proved that for each fixed value of \\(h\\geq 1\\), the problem of deciding whether ph(\\(G)\\leq h\\) holds for a given graph \\(G\\) is NP-complete, but deciding whether there exists an \\(h\\geq 1\\) such that the graph is pseudo-\\(h\\)-hamiltonian, can be done in polynomial time. This polynomial time result is based on the close relationship of pseudo-hamiltonian graphs with regularizable graphs. Some sufficient conditions for pseudo-\\(h\\)-hamiltonicity that are based on stable sets and on toughness are also presented. It is shown that the square of a connected graph is always pseudo-hamiltonian. For \\(d\\)-regular graphs with \\(d\\geq 3\\), there exists a threshold \\(\\tau (d)\\) such that for \\(h<\\tau (d)\\), it is NP-complete to decide whether a \\(d\\)-regular graph is pseudo-\\(h\\)-hamiltonian, whereas for every \\(h\\geq \\tau (d)\\), a \\(d\\)-regular graph is always pseudo-\\(h\\)-hamiltonian. Finally, the computational complexity of computing ph(\\(G\\)) on many well-known special graph classes is investigated: To decide whether a graph is pseudo-\\(h\\)-hamiltonian is NP-complete for bipartite, planar, or split graphs, but this can be done in linear time for partial \\(k\\)-trees and in polynomial time for cocomparability graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2714402$C2E6C06C-DD49-44B5-ABDE-BAFBD0B8E339","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2714402$AADB7353-F6A3-4768-A2D7-488BB75930FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pseudo-hamiltonian graphs","badges":[]}}}}}