{"entities":{"Q5937459":{"pageid":8114261,"ns":120,"title":"Item:Q5937459","lastrevid":47639491,"modified":"2026-01-02T07:05:30Z","type":"item","id":"Q5937459","labels":{"en":{"language":"en","value":"Hamiltonicity and circular distance two labellings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1619295"}},"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":"Q5937459$76D5ED7E-15B6-48B9-A8CD-6D6D502EFAD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00f2596b6f9581e171d32d88c1d52da5ce401719","datavalue":{"value":{"text":"Hamiltonicity and circular distance two labellings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937459$E382C8CD-5CA4-4632-9764-8BD2BB556E4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea23b006999b898a392da494d86820fac38e9403","datavalue":{"value":"0977.05078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937459$FD41FF16-8304-49C2-B394-F280E405BEA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7f893cb9f59889b4505e9e1beaa3cb07f5250b9e","datavalue":{"value":"10.1016/S0012-365X(00)00299-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937459$53C71AA9-A9AE-42EF-B5FF-73377F6CE6BA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18bb92565d9f2b332ec88013cd5ad6d4fda0b889","datavalue":{"value":{"entity-type":"item","numeric-id":189455,"id":"Q189455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937459$D0D507EE-0D3F-49B7-A540-87AEC9A8D1D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937459$374E997A-504B-442F-9616-82B52A5F7ABE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9e418580f2b70ce6849ba62f9449722e930b0d2","datavalue":{"value":{"time":"+2002-01-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937459$F928A152-A711-4682-B3D8-7ECD80DBA702","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab7883ba450e38fe02de7386b4aa534243c1485a","datavalue":{"value":"A \\(k\\)-circular distance two labelling of a graph \\(G\\) is a vertex-labelling such that the circular difference \\(\\pmod k\\) of the labels is at least two for adjacent vertices, and at least one for vertices at distance two. Given \\(G\\), denote \\(\\sigma(G)\\) the minimum \\(k\\) for which there exists a \\(k\\)-circular distance two labelling of \\(G\\). For a graph \\(G\\) on \\(n\\) vertices let \\(G^C\\) denote the complement of \\(G\\) and let \\(p(G)\\) be the path covering number of \\(G\\). The main result of the paper states that \\(\\sigma(G)\\leq n\\) if \\(G^C\\) is Hamiltonian; and \\(\\sigma(G)=n+p(G)\\) otherwise. Furthermore, the exact value of \\(\\sigma(G)\\) is given for \\(G\\) being a cycle \\(C_n\\) on \\(n\\) vertices, \\(n\\geq 3\\), or a Cartesian product \\(K_m \\times K_n\\), \\(m\\geq 2\\), \\(n\\geq 2\\) of the complete graphs \\(K_m\\) and \\(K_n\\), and for \\(G\\) being a graph of diameter two with a complement being Hamiltonian.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937459$D2E1A7A2-586A-468D-9E45-2332365ABF04","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":"Q5937459$FBAEB13E-3FB6-463A-89BC-CF08C195251A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937459$82E9D5C1-F1A3-4191-8745-FD4FAAB0213F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937459$D95FC11C-0517-4E3E-AEE3-1F0873ABF93B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93964f97bf92f1343b51d40f6ce7e8b90aab22fd","datavalue":{"value":"1619295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937459$EF01C74E-8D23-4DD6-BC06-590AAC95ED27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd53d393c376b85f274601d67e734a11b5e588d2","datavalue":{"value":"Hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937459$EA71E9B0-3522-4F75-8AFD-B1C4F3D66E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b40875aa5b690d44a88310768afde8b93cebc90","datavalue":{"value":"vertex-labelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937459$2C376A52-3340-46A6-A6FC-BE34CB7B99AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c077678df901cb62d85eaadaddb0c9f72d61f7ed","datavalue":{"value":"path covering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937459$245BBEFC-C84E-4DC1-A27B-1426071F27C9","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":"Q5937459$C0ECB64E-99BC-41C0-B71F-3A4C132DCDF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb27c73547173d3c7a327b97bf188702e21f1e68","datavalue":{"value":{"entity-type":"item","numeric-id":5463346,"id":"Q5463346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0fc891ab94726cb9c90754d28e8fa8176021ea1","datavalue":{"value":{"amount":"+0.8265159726142883","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":"Q5937459$771E4C73-B8A4-4759-BBBF-35287BB6DA4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4dee4ab9df43ed8e0f3ddac77b19eeb25f897fd","datavalue":{"value":{"entity-type":"item","numeric-id":5259049,"id":"Q5259049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"760d976f2022af947012668744edddad70231faf","datavalue":{"value":{"amount":"+0.7950654029846191","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":"Q5937459$137B15FD-94CA-4F12-9F1F-799B92884887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48f83cb82b403d358d5559411eeeb3872397ade3","datavalue":{"value":{"entity-type":"item","numeric-id":2829084,"id":"Q2829084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b47c5bc9a4d586776815602c197b9a960bb5636a","datavalue":{"value":{"amount":"+0.7917677164077759","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":"Q5937459$749D1A8B-4916-476A-9E7B-060885696BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4281b9a1608209b26f813501cf71aa84aa84a9b7","datavalue":{"value":{"entity-type":"item","numeric-id":1026152,"id":"Q1026152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ecc36e6b998012f208989fcf7bbed6e6def3658","datavalue":{"value":{"amount":"+0.7903137803077698","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":"Q5937459$91202943-D44A-494B-82FA-DE5C3FDBABF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fe7e30c6817a23912ab35586ef98328221e055f","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9652337f59ec4aa2a71eb544b1ce48bb90bbf37d","datavalue":{"value":{"amount":"+0.7899021506309509","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":"Q5937459$8349DBA4-FC30-4889-997F-6F9A7F18DAF8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937459","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937459"}}}}}