{"entities":{"Q896092":{"pageid":897940,"ns":120,"title":"Item:Q896092","lastrevid":65199315,"modified":"2026-04-12T00:58:33Z","type":"item","id":"Q896092","labels":{"en":{"language":"en","value":"A complete \\(L (2, 1)\\) span characterization for small trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6520412"}},"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":"Q896092$B5D20F2A-30F3-4CBC-8799-3A1B488A6501","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"71ab18a0f701d716c7169b19824ecb67eb7259ff","datavalue":{"value":{"text":"A complete \\(L (2, 1)\\) span characterization for small trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q896092$15396C32-B1AF-40EC-A3AD-0628A57940E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a76bf2ac4a53b38b7cada85c476b5a77c7233104","datavalue":{"value":"1332.05125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$86F8F5CC-0EB6-49D2-94D7-7E842B799C75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6e87fde3196f9dc6c2c9d6864757b9c0ab15c5c","datavalue":{"value":{"entity-type":"item","numeric-id":896091,"id":"Q896091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$C39E76FF-4CC5-4BC2-984E-43BBB6582BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3be463567e73f36c9d372721cfc618e65084396","datavalue":{"value":{"entity-type":"item","numeric-id":381187,"id":"Q381187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$B4269377-4E61-427D-A5E1-CFE33BC967A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$B9253078-1E2B-4956-95D3-4EBB99C729A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f98ff43191c7d2cedf25947a17beeb973f5b0c2","datavalue":{"value":{"time":"+2015-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q896092$4F1961F6-52E4-495E-BBA1-69AD1A0BD295","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a492eb45333d3843627b2c6d05903aac5e1fcea7","datavalue":{"value":"An \\(L(2, 1)\\) labeling of a graph \\(G\\) is a mapping \\(f : V (G)\\) to the set of nonnegative integers, such that \\(|f(u)-f(v)|\\geq 2\\) if \\(uv\\in E(G)\\) and \\(|f(u)-f(v)|\\geq 1\\) otherwise. The span of an \\(L(2, 1)\\) labeling \\(f\\) on a graph \\(G\\) is the maximum \\(f(u)\\) for all \\(u\\in V (G)\\). The \\(L(2, 1)\\) span \\(\\lambda(G)\\) of a graph \\(G\\) is the minimum span of all \\(L(2, 1)\\) labelings on \\(G\\).  \\textit{J. R. Griggs} and \\textit{R. K. Yeh} [SIAM J. Discrete Math. 5, No. 4, 586--595 (1992; Zbl 0767.05080)] showed that \\(\\lambda(T)\\in \\{\\Delta(T)+1, \\Delta(T)+2\\}\\) for a tree \\(T\\) of maximum degree \\(\\Delta(T)\\). \\textit{G. J. Chang} and \\textit{D. Kuo} [ibid. 9, No. 2, 309--316 (1996; Zbl 0860.05064)] provided a polynomial-time algorithm that can decide whether or not \\(\\lambda(T)=\\Delta(T)+ 1\\). In the current paper, the authors present a complete characterization of \\(\\lambda(T)\\) for trees \\(T\\) up to twenty vertices in terms of forbidden subtrees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q896092$57AC1C6A-837C-4032-947E-1E090F01FC75","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4833c1e83671332887f7a1a1eb973ba301cbf10a","datavalue":{"value":{"entity-type":"item","numeric-id":244910,"id":"Q244910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$AB280BFC-7272-4567-833C-6D4F6E01F752","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$5DDFC62A-63A9-4E64-845E-14955E8B322A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$59E7B632-D17A-467C-9E18-D97AAC23F521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$83B140AC-AC73-44FD-967A-85143DA5BE07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0f5d891499bf740f04dbca840248a80fdc900b1","datavalue":{"value":"6520412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$FCE4E73F-9806-4E6A-89F6-3230D1ED3ED4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d71ff41485748ce2d4eed71a2ccf63f8ea2b3c05","datavalue":{"value":"channel assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q896092$A74C9184-74A8-49D3-AD08-50B70DE4AA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ab95bb98beacdfece52edf77a9380387d77c400","datavalue":{"value":"\\(L (2, 1)\\) labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q896092$15CD3058-44EC-4E28-8955-F8FF8008F371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8cb37184250090febaa18ce7894ad89c69b602c","datavalue":{"value":"Chang-Kuo algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q896092$B5F47480-DF07-48CC-B65F-2F9FF47D3AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bda7dc665615e690d013ff251794b24adbce2f9","datavalue":{"value":"forbidden subtree characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q896092$57F07409-1BB5-4FF5-BDEC-835979C3349D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"58012661cd5902d08c1d307a106ffc22f40d0c6b","datavalue":{"value":{"entity-type":"item","numeric-id":13366,"id":"Q13366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$536361C0-4D05-48D2-AF15-C3E9065F8B75","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":"Q896092$379A46AE-3CBE-49E5-A719-9E6782DCBE8D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9bfbbf8b1d05f3283979ef8c4cb3ce8538e5f1c5","datavalue":{"value":"https://doi.org/10.1016/j.akcej.2015.06.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q896092$45D87322-FD41-47BC-B262-CBC6E8C99F9E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a034290ca7b5adae63b146e1c9543943bc4ae2a","datavalue":{"value":"W2198873357","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$0E29E8A9-7690-4F9D-BFAF-3BC182614F5D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$EBA58C30-90D8-49DB-B873-16F34D5F054F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a026cd0f4b7a301bb63b3a31e47f3cb40412d167","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$956AD75D-BA75-45EC-93EB-A7485E914326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e7ebe5bc0bdc8dcc852303bb0c68c66f87ed642","datavalue":{"value":{"entity-type":"item","numeric-id":2375957,"id":"Q2375957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$219834E7-F3BA-4C58-A8D2-210CE96EFA64","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c02e25e416b1c8c5037247999942057f0e73dc5b","datavalue":{"value":"10.1016/J.AKCEJ.2015.06.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896092$580CDF10-5ECB-46E1-8137-68F94502E357","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61ef3409029b33fbc529af823c98e1c98963d6ab","datavalue":{"value":{"entity-type":"item","numeric-id":2489954,"id":"Q2489954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11a7ec59755461d3e4cd59f8618c59885fb92b46","datavalue":{"value":{"amount":"+0.8934382200241089","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":"Q896092$1B610973-4828-437C-BA33-E0D1BB549AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9af3f5d1c6dad7d41ed31d2333850c0b693106","datavalue":{"value":{"entity-type":"item","numeric-id":2364083,"id":"Q2364083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e4bc086c0b226f2b2d157921008a2519dfec1db","datavalue":{"value":{"amount":"+0.8880457282066345","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":"Q896092$31A5B48E-8DBA-4616-B193-1384CFE0256C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b844b6e9f4a8eb34f2531d513d317ba7fe74ef5d","datavalue":{"value":{"entity-type":"item","numeric-id":2983505,"id":"Q2983505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87d3c6fd66c3e1f3bc9b6192bbf63de96be3fd33","datavalue":{"value":{"amount":"+0.880187451839447","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":"Q896092$4211020A-013A-4523-97EA-141AC3B9F8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88147637db83da758d54b586742e370916233e24","datavalue":{"value":{"entity-type":"item","numeric-id":837161,"id":"Q837161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a259bef37ac410b96035ef6adca65fd791ef4446","datavalue":{"value":{"amount":"+0.8663316369056702","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":"Q896092$55BBFDDC-D9DB-46DB-A259-6938CC0CB748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84d1ef4ad975218a4878ca745c102e02def4d3ab","datavalue":{"value":{"entity-type":"item","numeric-id":5920600,"id":"Q5920600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"445f35e953b99aa0bd168fd80edfdc56b8a77d2e","datavalue":{"value":{"amount":"+0.8659871220588684","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":"Q896092$470D7FE4-E072-4E85-962A-4CBC0BC12B42","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896092$7B404AC0-1313-401F-A76F-033DE138D488","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complete \\(L (2, 1)\\) span characterization for small trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complete_%5C(L_(2,_1)%5C)_span_characterization_for_small_trees"}}}}}