{"entities":{"Q1971217":{"pageid":1981959,"ns":120,"title":"Item:Q1971217","lastrevid":82119467,"modified":"2026-05-06T20:08:56Z","type":"item","id":"Q1971217","labels":{"en":{"language":"en","value":"Pseudo-Hamiltonian-connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1421663"}},"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":"Q1971217$D884A628-540D-4E1D-9B7B-245795C3DA5C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cefb6e92e4f400899d391257d1db396cc4d0a97","datavalue":{"value":{"text":"Pseudo-Hamiltonian-connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1971217$DFEBF5A6-954E-4FED-B0AC-2B284B24598C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42631d144f3123abc7d2a6f23b2f63395a1d6608","datavalue":{"value":"0939.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$E46DF1B7-56E7-43B4-85F8-E6DAE13DB4A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"810d126be1986556efd861371d6d3f462d5c494f","datavalue":{"value":"10.1016/S0166-218X(99)00181-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$6EFDF111-6DBC-484D-8810-8FA17BFB0D33","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$F465E79A-9852-4DC7-8E34-AD6EB56C8A07","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a607f304712b79d2eec9848961c4d4b0d86f1fee","datavalue":{"value":{"time":"+2000-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1971217$2C91C1AE-CDF4-43FC-BA9E-BC4935CBA6AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4533b3132ba1c6c25c237fed6bffd71e39434ff1","datavalue":{"value":"A graph \\(G\\) is called pseudo-\\(k\\) Hamiltonian-connected if the associated graph \\(G[k]\\) (obtained from \\(G\\) by replacing every vertex by an independent set of \\(k\\geq 1\\) vertices) is Hamiltonian-connected. The main result says that certain six statements are equivalent, where one of them is the question of pseudo-Hamiltonian-connectedness and another concerns a beetle problem posed by R. Nowakowski. This characterization and its proof provide a polynomial time algorithm answering these questions. The studied problems are related to several other notions (vertex packing, Berge's regularizability, 2-bicriticality, and toughness). The NP-hardness of an efficient beetle problem is proved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$510D1506-3841-40C5-943B-E31A5BAD49FB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$1847A326-9F9D-4796-AA09-6A94F646B58C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$620B044E-04EB-47D1-8C8F-377698E7811A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$C3D2CD3F-A0E7-4D22-8C66-9721683AE6C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$A244B8F8-A413-4915-938B-5835DB6E1057","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1111fd3808b7d7be6cb9c23ada87cd468088bcf","datavalue":{"value":"1421663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$472B693D-039B-4E0F-9ADC-E9DE62CDD9C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"213d7ade7a6349aba9d1c3092c5082d8a5b2d3ef","datavalue":{"value":"pseudo-Hamiltonian connected","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$0A4E83DA-A62D-4F7A-AEEC-290D56567D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a616ee0fa0cc3d10db61a96aa0fcd0be97f7d8fe","datavalue":{"value":"regular Hamiltonian walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$D983F8CF-1BF8-4647-9307-16D887C4F967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b9089ae19922882da9d39bd703fdcaf0c930402","datavalue":{"value":"beetle problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$E4584F80-BABE-4782-B7D1-78BE0C2E21BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ac3d4aa0b6147605e0d11fde19d86ae13070cd6","datavalue":{"value":"vertex packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$AF3FE6E9-ADF5-4E30-9355-016EA01C07C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e44dd1e6936b56b8be53695af32de5196528944","datavalue":{"value":"regularizability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1971217$57A65E4C-F88F-4113-9B57-78AD1BC17C9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$327ABDA9-A94D-4A06-8010-793E3ED554F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$047305E0-56A3-4BAF-B16A-607AD6741918","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":"Q1971217$AB2AA400-35BF-4FCE-8E05-887CF36589C0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbdb7fb6bfc6605fba8e084b78e77890f773e958","datavalue":{"value":{"entity-type":"item","numeric-id":4163564,"id":"Q4163564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$E3EB67BD-2BEF-414C-B0C9-C1EF23214C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$AC4308EE-FEA8-4101-82FA-27180473484E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$98C5D6E3-14F7-4158-9A9C-99C55C04DB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$675B9474-2CC3-40EE-B69E-4E6EC3D50708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"615b6090623e2fe14c484a0a9e32f6c50e8e26da","datavalue":{"value":{"entity-type":"item","numeric-id":4136929,"id":"Q4136929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$EB8EE413-040D-4921-81AE-B9FE68E37D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1b2bae496191c5e59eed7096ad0bc88ae12d3eb","datavalue":{"value":{"entity-type":"item","numeric-id":3325758,"id":"Q3325758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$7D8323B6-FA9E-41CA-B537-01A1B39BD297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fc9e1ef40099bd91f215d0bf6b6055f47a1cc7f","datavalue":{"value":{"entity-type":"item","numeric-id":3050138,"id":"Q3050138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1971217$18C5D75A-37B3-4775-84C0-138DC3455C8C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1791207baf8e981189a2bf3e2549648e0261fad1","datavalue":{"value":"Q126671684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1971217$0FD7A07A-A8C7-4AFD-B098-467880AD1B53","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":"01b88e3eb0f584dd97be2c59205effe80b91e802","datavalue":{"value":{"amount":"+0.7959607839584351","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":"Q1971217$36AB84E6-2907-49E0-8397-031C89EF5F19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"152301bea8f19b868525e487ac07511eccf37de0","datavalue":{"value":{"entity-type":"item","numeric-id":2714402,"id":"Q2714402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b17f759e566a5393cd39f55bd32b44cf676736f8","datavalue":{"value":{"amount":"+0.7952868342399597","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":"Q1971217$8E31D497-4F48-442A-9672-5298653069D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ff3991c446dbe7cd5e53717f44ec8631baf8cdd","datavalue":{"value":{"entity-type":"item","numeric-id":2497487,"id":"Q2497487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd3ba94ac0b8a60b96882be6ba36ab3d66b83be1","datavalue":{"value":{"amount":"+0.7214776873588562","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":"Q1971217$08D80099-E562-4C28-B6B8-466900B8575F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6677d4eae652dc192cf9ecb31211d3d316f30eb6","datavalue":{"value":{"entity-type":"item","numeric-id":4500611,"id":"Q4500611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ec3b19a53fbf2ddcef2bd1d7c0590af2c5934cb","datavalue":{"value":{"amount":"+0.7173237204551697","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":"Q1971217$DF9F9535-BF88-41AD-BE7B-70B215525F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23e4c2ed4308f62c30efffd201e27ec763349905","datavalue":{"value":{"entity-type":"item","numeric-id":4227908,"id":"Q4227908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ec3b19a53fbf2ddcef2bd1d7c0590af2c5934cb","datavalue":{"value":{"amount":"+0.7173237204551697","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":"Q1971217$997198EB-EF59-41A0-8901-69747B684C43","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Pseudo-Hamiltonian-connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Pseudo-Hamiltonian-connected_graphs"}}}}}