{"entities":{"Q1892831":{"pageid":1903573,"ns":120,"title":"Item:Q1892831","lastrevid":69207801,"modified":"2026-04-13T05:28:39Z","type":"item","id":"Q1892831","labels":{"en":{"language":"en","value":"The square of paths and cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 767680"}},"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":"Q1892831$07D55ED6-C105-4822-AE0E-B8B49347ABDE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1342ba33da8039534bf3f83891f082283e519d1e","datavalue":{"value":{"text":"The square of paths and cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1892831$3E9BA6A4-C1FB-4B0D-BDBA-6905E2804525","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"be8b93b300e779f08fcfa972f65437326de868fa","datavalue":{"value":"0826.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$6413B7E6-7F89-43D1-9481-CEDB922D6DAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892831$C4A351D0-F3DD-44CE-B271-446F1B0595F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89939404571a8a457f4efe42bf31156c65cd7105","datavalue":{"value":{"time":"+1995-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1892831$393534CA-B8DD-4500-A1CF-A62EDB088BE6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ee1ff74966c0563062b03cd925da769e6d59093d","datavalue":{"value":"The square of a cycle (path) is the graph obtained by joining every pair of vertices of distance two in the cycle (path). Posa conjectured that if a graph \\(G\\) on \\(n\\) vertices has minimum degree \\(\\delta(G)\\) at least \\({2\\over 3}n\\), then \\(G\\) contains the square of a Hamiltonian cycle. The main result shown here is the following: Let \\(G\\) be a graph on \\(n\\) vertices. For any \\(\\varepsilon> 0\\), there exists a number \\(m\\), depending only on \\(\\varepsilon\\), such that if \\(\\delta(G)\\geq ({2\\over 3}+ \\varepsilon) n+ m\\), then any two independent edges in \\(G\\) are joined by the square of a Hamiltonian path in \\(G\\). Consequently, such \\(G\\) contains the square of a Hamiltonian cycle. The proof uses a lemma of H\u00e4ggkvist on 3-partitioning the vertices of a graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892831$D4A8C352-52C3-4330-843F-9BDA0DA5574A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892831$1B8D5BD5-9550-4DA1-8998-09CABA69A326","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$76A40813-2BCA-40B7-9EFD-12DA5A8DAE3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$117146D0-778C-4004-B738-DDE6F3C6C062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$6E397D30-76FF-45B6-B36D-6F78BA7FA4EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce322c1be665105d04b9e06618e1ba068485f01e","datavalue":{"value":"767680","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$99F772EE-F222-4E46-8454-C08B7124B923","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a80b6718acb18ad1859f621fd47cf3951c581e3","datavalue":{"value":"square of a path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892831$C0808057-0169-4DF2-A189-AC9858A62300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"275912919977c9c9b42ac0c6bda6392ce608f733","datavalue":{"value":"square of a cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892831$274BE3A9-A2D5-45FA-938C-562901DA947D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892831$35CC9C83-5416-4969-A66D-4F1923C675A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892831$F1CF0995-2B86-4351-ACAA-F57BCAC9AA5C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dcef5d234452468504af97acb02bd778ed8b8dd3","datavalue":{"value":{"entity-type":"item","numeric-id":801081,"id":"Q801081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892831$2ED96A9C-090B-428E-8142-4610C30E6E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8e4763e432b6ffd9ef1ff20256862696bdf24ca","datavalue":{"value":{"entity-type":"item","numeric-id":555495,"id":"Q555495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892831$EBEE7FD2-5C09-476B-9B1F-D2AA038D6C72","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":"Q1892831$060B24F7-6772-412B-8237-16C340D5F29B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2876ae8fb865d9b19ebf0be49774dd8ce6110eaa","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1892831$87BE7E04-70F9-47DA-9215-06940F31F755","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0463b62d7b9636a13a0e39c3978805bc9950478","datavalue":{"value":"W2066235086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$F8AD74E1-2961-432E-AE13-18D7689E52CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ac37c2d16f62110bb9211c0e61777cc09f8a768a","datavalue":{"value":"10.1006/JCTB.1995.1005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892831$A4C462B2-D54C-49A5-8619-35FD40C927D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caa592260402ffa033c7b03fb76d16e68ce3a911","datavalue":{"value":{"entity-type":"item","numeric-id":4296514,"id":"Q4296514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1833eacc02f64b8cbed6451ad9490bc0ddb4c07","datavalue":{"value":{"amount":"+0.9152012467384338","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":"Q1892831$42F07907-4ADF-49E2-AFBE-4EE03E64E205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ea856f96b1b24fc4e707485422ddcfe9c559f3","datavalue":{"value":{"entity-type":"item","numeric-id":4894609,"id":"Q4894609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0e7bbe78768adb130290629a54ec31b3afd57e1","datavalue":{"value":{"amount":"+0.9105385541915894","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":"Q1892831$91C7B55D-BABC-411E-A61F-AE5AC3CB2498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"391d3722c99a4c4ca9143eb9f386593ac6c4d469","datavalue":{"value":{"entity-type":"item","numeric-id":4715278,"id":"Q4715278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"818ddb829875c5828e56689c3c49fcca204439d8","datavalue":{"value":{"amount":"+0.8991361856460571","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":"Q1892831$615B30BB-7A8C-43FA-9735-A84C98D0249C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The square of paths and cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_square_of_paths_and_cycles"}}}}}