{"entities":{"Q1567607":{"pageid":1578347,"ns":120,"title":"Item:Q1567607","lastrevid":74300724,"modified":"2026-04-14T19:25:32Z","type":"item","id":"Q1567607","labels":{"en":{"language":"en","value":"On \\(L(d,1)\\)-labelings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1462273"}},"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":"Q1567607$9FE072A1-6D4A-4B7C-9E65-2DC74CEBFFA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac847a64c2a3b90d9888e20502897ea8f0c1100f","datavalue":{"value":{"text":"On \\(L(d,1)\\)-labelings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567607$4DC015DF-D393-448A-B1D2-C423BA0106A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f1291ec199410c2ad8fe6d278a99677d08562b6","datavalue":{"value":"0954.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567607$2C0D7594-FACB-4F9A-992B-258735D260A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6f6628a52dea12d8bcd599b3d777e6898866933","datavalue":{"value":"10.1016/S0012-365X(99)00400-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567607$57306738-3323-4187-A0A5-B02D23EF7D3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68394fd7e8a253e114d6399606d47416a190b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":1511313,"id":"Q1511313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567607$D217BB76-6254-4AB9-BDC7-F03FF6F31EE8","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":"Q1567607$2B6CAD14-AC6E-4630-8B2E-6631A288D6F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d1d54670924db26a74d9a3b5e6224e9f60db0e3","datavalue":{"value":{"time":"+2001-01-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":"Q1567607$141242B7-0D0C-4334-8C01-DB6F6A3BFE77","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"68064e788f2206b5132a996cd61d673d54b9b777","datavalue":{"value":"For a graph \\(G\\) and positive integer \\(d\\) an \\(L(d,1)\\)-labeling of \\(G\\) is defined as a function \\(f: V_G\\to {\\mathbb{Z}}^{i\\geq 0}\\) such that \\(|f(u)-f(v)|\\geq d\\) if \\(uv\\in E_G\\) and \\(|f(u)-f(v)|\\geq 1\\) if \\(uv\\not\\in E_G\\) and \\(u,v\\) are connected by a path. The \\(L(d,1)\\)-number of \\(G\\), \\(\\lambda_d(G)\\), is a minimal number \\(m\\) such that there exists an \\(L(d,1)\\)-labeling \\(f\\) of \\(G\\) with the image \\(\\{1,2,\\dots,m\\}\\).    The authors extend the study of the number \\(\\lambda_d(G)\\) from the extensively studied case \\(d=2\\) to arbitrary \\(d\\geq 2\\). The main result is an upper bound \\(\\lambda_d(G)\\leq \\Delta^2 + (d-1)\\Delta\\) for any graph with maximum degree \\(\\Delta\\). More specific results (lower and upper bounds) are obtained for chordal graphs and their various subclasses, in particular trees. It is shown that the bounds for trees are attainable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567607$73010B4A-9125-4AC7-AC17-3F6A9D96367B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567607$F5CC1109-DFCB-4D8E-9AA6-BC1362B77133","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"370356b1f34d6fff116ce3bad0353c7e4ef07eb1","datavalue":{"value":"1462273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567607$D1164ED7-EBE2-40B1-A6FE-4B2ED3F274AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a594ef9dbe8a090d158483294abcbc56f4589f9b","datavalue":{"value":"graph labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567607$D08396E9-9C3D-4B30-9F5A-31C1344120E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6a050984477f85ff5f0e6bc821d935cb5cfc07c","datavalue":{"value":"vertex-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567607$2D9D6C87-AB74-4C00-9406-859C6E0ECAF5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567607$CE8674F3-5777-4F3F-AF24-AD09FE6C53F0","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":"Q1567607$60AF150E-B71E-465D-B62F-4B1F9C032740","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"07da8a3c81b5120b21da7f8730937dfcf6e3e8a3","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00400-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567607$DF3D732E-8B1B-4841-8997-4AA3AB27A0FF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"348c9e9231799dfc4e6fee7108fcc61b9ae28aca","datavalue":{"value":"W2058787498","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567607$973BFF72-DA64-4E0B-8359-9FE8D66CEF16","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7ce7edc1c4296b70d5f8a440557c91166c33dff","datavalue":{"value":{"entity-type":"item","numeric-id":3052501,"id":"Q3052501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82f9ee6cc3e36ac79b4b1f5a4b993e50be7409c4","datavalue":{"value":{"amount":"+0.9860774","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":"Q1567607$E0F6007D-C3BE-4BA7-AAB0-8F3FF74C3BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e9c6aebb6e6628b4edb1b51b0b279e48f02cdb9","datavalue":{"value":{"entity-type":"item","numeric-id":2476282,"id":"Q2476282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f180c5d42bef06772d8b1b7dbb4736c97ad41be6","datavalue":{"value":{"amount":"+0.97588044","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":"Q1567607$AA3107E5-7D80-4A75-BC9E-9C7699D916A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ef7f2d8c34b0d76da9e8e34ca9894373427e8eb","datavalue":{"value":{"entity-type":"item","numeric-id":3576665,"id":"Q3576665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bea4f03cf08e6218caad351669439bd2885955c","datavalue":{"value":{"amount":"+0.9758803","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":"Q1567607$B2A221D2-1F3C-4D8A-A77C-BDF49F529BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a40b5a184961e7dab889e4306c55887ba2c80a00","datavalue":{"value":{"entity-type":"item","numeric-id":4468997,"id":"Q4468997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f927a73f9b5c0a2c4d213e0f036ef16a6900a677","datavalue":{"value":{"amount":"+0.96424073","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":"Q1567607$9C404DAF-280F-4B33-9CB9-CA1C2CA0AF84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d36934ab0d7ee0f07ee08814133008b6852a141","datavalue":{"value":{"entity-type":"item","numeric-id":3441561,"id":"Q3441561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"999ad03a19f53983737f57d3aca837adab386295","datavalue":{"value":{"amount":"+0.9574231","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":"Q1567607$475323C7-13B1-4710-8267-EB838EFE0C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"716ca5c5d6d3d344906c4e6675e4b48fa4407ac9","datavalue":{"value":{"entity-type":"item","numeric-id":4657607,"id":"Q4657607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba24ea3fbeddd1e9797df28df159302296ca7598","datavalue":{"value":{"amount":"+0.9529147","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":"Q1567607$BBC9845B-C9D6-45F6-85E6-7B63F1A0FAEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23054bd72c75ee9483b6bf3f0b0958bd1f8a3250","datavalue":{"value":{"entity-type":"item","numeric-id":5468089,"id":"Q5468089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8279b61a39f9ffca50a6fe19539afaef511bda","datavalue":{"value":{"amount":"+0.9517483","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":"Q1567607$9E7C2100-4D52-4924-BA9E-5A1C0751249A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38a78344298faface95e5b036a15231297cb1258","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10a1fb30f2c3185f39787b31029950eebbb7b719","datavalue":{"value":{"amount":"+0.94614255","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":"Q1567607$078D9C27-5CC4-4A0D-8F15-3EC642C34FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28543c39cff8e8a489f7c7d13308db7ef6881e22","datavalue":{"value":{"entity-type":"item","numeric-id":449571,"id":"Q449571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a45748e0514380642760f3da4dc42ffd8f46aa1","datavalue":{"value":{"amount":"+0.94243735","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":"Q1567607$17596BCD-7DF1-41D7-9552-1E54D981CB74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adbb657c0b676f06a0947b5b1f37058c1a5c2e08","datavalue":{"value":{"entity-type":"item","numeric-id":5432807,"id":"Q5432807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0389ef1a81377748dd21a97b6e8714d4abcd6ca9","datavalue":{"value":{"amount":"+0.94129777","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":"Q1567607$383B2A1C-8AC4-465E-AADD-63D738B09D03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On \\(L(d,1)\\)-labelings of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_%5C(L(d,1)%5C)-labelings_of_graphs"}}}}}