{"entities":{"Q1805009":{"pageid":1815751,"ns":120,"title":"Item:Q1805009","lastrevid":46367208,"modified":"2025-12-24T15:47:44Z","type":"item","id":"Q1805009","labels":{"en":{"language":"en","value":"Hamiltonicity in graphs with few \\(P_ 4\\)'s"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 751368"}},"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":"Q1805009$C0BED865-EE3E-48C7-B6B8-9DE3C8D1FA1F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c8cab1e33b6feb3df40b22d39abd7f49ab258f5","datavalue":{"value":{"text":"Hamiltonicity in graphs with few \\(P_ 4\\)'s","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1805009$456A7140-CD27-4FDC-8C61-BF702FB793B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d5c728631d8e315560a23ea8bd5213e373158ad","datavalue":{"value":"0819.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$5CFF657E-67AF-4FDC-899D-3CD3E5EEEA80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ccae3c59d57a94a172e191e5756f2400fdf41a3a","datavalue":{"value":"10.1007/BF02253613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$EBCB3AEF-EFF6-4C1C-A1C9-555F018EB20E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"333e7366b859c9d0894f9d970904d38f74882167","datavalue":{"value":{"entity-type":"item","numeric-id":271596,"id":"Q271596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$EF60FE74-35C2-4BB3-82B0-32D3DA517A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a04ecc81832bff993b189ec55412cfe64658861b","datavalue":{"value":{"entity-type":"item","numeric-id":196797,"id":"Q196797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$42111024-1841-4D3B-9CD5-76CE66882022","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$C21B2C3A-F235-478E-B09D-2EB201255058","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c305b7fdcb11f411e5b2568d002c13123a59fe2","datavalue":{"value":{"time":"+1995-08-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1805009$24BB8DD0-66E4-4BA6-A64B-37CE135CDA3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b5cd2ea39d101399ca1a326acb3e04dea7c55d97","datavalue":{"value":"R. Jamison and S. Olariu developed, starting from an extension of the notion of cograph, a theory of decomposition of graphs into \\(P_ 4\\)- connected components. It turned out in their work that the algorithmic idea to exploit the unique tree structure of cographs can be generalized to graphs with simple \\(P_ 4\\)-structure. This paper shows that deciding hamiltonicity and computing the path covering number are easy tasks for \\(P_ 4\\)-sparse and \\(P_ 4\\)-extendible graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805009$399C9225-CAA3-4FC4-A60E-BE0E5C1D1D8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$335B25D6-1734-4D87-B2B5-343EB9329769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$BDC9CB1C-72D7-4A7A-881C-B8022761641F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$0A9007F0-3006-43D1-915D-D933F9B28BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$E36C55F6-BBFD-4DF3-AC20-DA29FB2BFD65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4673a1ab13cfdaae481c5eb66925374a6e1ef7c9","datavalue":{"value":"751368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$604D23E0-12FD-4AF2-B104-8D97403AC005","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9a04a453e91c79c7e831d838f6c5e3a9e0859a2","datavalue":{"value":"scattering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805009$C5EB6121-48AA-4E4A-AF80-2932F8799F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24e5ed3f0abc29a7b282dcc25b70014d35ec3b1d","datavalue":{"value":"\\(P_ 4\\)-structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805009$2B381BDC-D2A0-452B-83D7-472D123DCE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad7f6c16e18413af432f8e820582fb2aa296646","datavalue":{"value":"hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805009$A9DB0E18-1151-4D22-B7D0-46E5557AB84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c077678df901cb62d85eaadaddb0c9f72d61f7ed","datavalue":{"value":"path covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805009$826C5328-66E2-49E3-86E0-D3BAA48EB948","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":"Q1805009$9D5AEC67-39FB-4A7D-A60C-9DC5E68D1330","rank":"normal"}],"P223":[{"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":"Q1805009$E9323FCD-C9E1-4C36-899C-1E610BCF302E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$F72A5B79-AB9B-4FDC-8021-DDB4038C55B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$A3DF52D6-450B-413D-943A-EFA987EEA4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e0dfd1e1d40529f667794361f35711c50787a65","datavalue":{"value":{"entity-type":"item","numeric-id":3476849,"id":"Q3476849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$EEEA1136-660B-4144-9F21-AA13AB7AA17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b7031de21cde61633337fab3cf39e01ee3cc05","datavalue":{"value":{"entity-type":"item","numeric-id":1182318,"id":"Q1182318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$359B54BC-DF20-482F-A099-F08C5B51E5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b2998788fd5c6bb689ab64483e3a026a3e293a","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$1A57096E-0119-4B64-8050-50BCBC52D548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31403449edcb685befef57967c6d318e33df55c0","datavalue":{"value":{"entity-type":"item","numeric-id":1247984,"id":"Q1247984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$57FC878E-6CCC-4DD8-9F62-2FB733D1594A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13c295423ec3d91cc1979ebb1d42d8adc698a8bf","datavalue":{"value":{"entity-type":"item","numeric-id":1903198,"id":"Q1903198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$7875B766-32E2-43F3-939E-91CC9FA9ACDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c4072136d9221c8375ceb902dbe28d118e87046","datavalue":{"value":{"entity-type":"item","numeric-id":4819984,"id":"Q4819984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805009$A0288BEF-2B12-4521-97B3-5BACCED4D87A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e7060e9e5a76848f3775db82b6a1ce90cab0d67","datavalue":{"value":"https://doi.org/10.1007/bf02253613","type":"string"},"datatype":"url"},"type":"statement","id":"Q1805009$72AED591-9E20-43AF-8784-1E09FD736132","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3075c3b1d6c4efb5608214784d68da989e5820b2","datavalue":{"value":"W2025795635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805009$4412DD1C-BD8A-442C-9A38-7DE0BA9815B4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ba6d5243eb654e25f1ef41d591e19e588f8e15","datavalue":{"value":{"entity-type":"item","numeric-id":1390873,"id":"Q1390873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be21a8029eac1327c3867006bf39e1b234500c59","datavalue":{"value":{"amount":"+0.7765150666236877","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":"Q1805009$196B4475-CD4C-47DE-889B-C2A85F4FE7D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea781d2b4b1b63c6e4ca66c22f288eb84ac9821f","datavalue":{"value":{"entity-type":"item","numeric-id":1897361,"id":"Q1897361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faa82d50917e285e44a183b6b01e7a8f5d33bb5d","datavalue":{"value":{"amount":"+0.7600380182266235","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":"Q1805009$3618CA27-FECC-4A55-9764-827D62509913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d25c5eba43604591db7523bc06f49b4c46c1515","datavalue":{"value":{"entity-type":"item","numeric-id":3836509,"id":"Q3836509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad563210ea4243d092dca467757e0578b92c3711","datavalue":{"value":{"amount":"+0.7583194971084595","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":"Q1805009$C45E6D70-05FD-4376-AC29-0ADB3B242305","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1805009","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1805009"}}}}}