{"entities":{"Q856879":{"pageid":858727,"ns":120,"title":"Item:Q856879","lastrevid":42727236,"modified":"2025-07-09T14:56:21Z","type":"item","id":"Q856879","labels":{"en":{"language":"en","value":"\\(\\alpha\\)-labeling number of trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5080071"}},"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":"Q856879$C421874F-9B8E-4552-AAE1-841C6EAE95BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"256322dc2d4e9d15c4e10cd70066884e424a697f","datavalue":{"value":{"text":"\\(\\alpha\\)-labeling number of trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q856879$CF1F3E20-8A65-494E-8C1B-DF3246BBB8AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e3922af7734d57d3e74070059ea60ddfffab818","datavalue":{"value":"1106.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$CFB69136-A715-4261-8110-94F88416FB8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90a9c5dfae259f709985a2bb4f1728baad12a6bc","datavalue":{"value":{"entity-type":"item","numeric-id":856878,"id":"Q856878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$2C2E1982-D3BA-41DD-9C4D-7237F08EB8B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b902cf7188cb5748bebfd7978ab7d636721b1781","datavalue":{"value":{"entity-type":"item","numeric-id":439195,"id":"Q439195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$917A4326-A162-4764-84E8-5852A3003C76","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":"Q856879$6005F8D9-9C67-4CDD-A1A3-6D16B4E702F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0f104b4da63c9b7ec094905bf1c1c3559eeb80a1","datavalue":{"value":{"time":"+2006-12-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q856879$B826AAA0-9917-4ED7-86AC-9D8551C8DAFF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b8a0fdc4b56a6f72675d7e1027c11090225309cc","datavalue":{"value":"This paper is concerned with \\(\\alpha\\)-labellings of graphs, introduced by Rosa in the 1960's in connection with the decomposition of complete graphs into trees. Due to the difficulty of Rosa's problem, a number of variations have been introduced. In relation to one of these, the notion of the \\(\\alpha\\)-labeling number of a graph was introduced by Snevily in 1997. \\(H\\) is a host graph of \\(G\\) if \\(H\\) has an \\(\\alpha\\)-labeling and can be decomposed into copies of \\(G\\). The \\(\\alpha\\)-labeling number of \\(G\\) is defined by \\(G_{\\alpha}=\\) min \\(\\{t \\mid\\) there is a host graph \\(H\\) of \\(G\\) with \\(| E(H)| =t| E(G)|\\}\\). Snevily conjectured that for a tree \\(T\\) with \\(n\\) edges, \\(T_{\\alpha} \\leq n\\) and proved that \\(T_{\\alpha} \\leq 2^{n-1}\\).   The first author of the paper at hand improved this to \\(T_{\\alpha} \\leq e^{O(\\sqrt{n\\log n})}\\). In the current paper this is improved to the quadratic bound \\(T_{\\alpha} \\leq \\lceil r/2 \\rceil n\\), where \\(r\\) is the radius of \\(T\\). The proof is interesting and constructive in the sense that it involves definining an actual family of graphs with \\(\\lceil r/2 \\rceil n^{2}\\) edges which serve as host graphs of arbitrary trees with \\(n\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q856879$A9C1DF97-F710-4370-96DC-1E93E69E78AF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a05a759299228196328c377cffbb2309b88267fc","datavalue":{"value":{"entity-type":"item","numeric-id":186182,"id":"Q186182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$CC3E14B7-6434-4176-B037-8E79120DB3F8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$E74D1B43-8646-4D9D-AF6A-685C88C1714E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$E956F5E4-D713-4C2C-A894-B413823C9896","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ddcda3914a2e9b02bc17853b60d36a6af555c722","datavalue":{"value":"5080071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$61DE689E-2427-4BBD-8F0C-C7C5C40BCA16","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q856879$0A5952DF-2C1E-42D8-B100-B0D0EC7525F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q856879$52501E38-DF67-4975-93C8-444EABD26B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9330a004979748f3244c0ce03b3992f1f8de4131","datavalue":{"value":"graceful labelings","type":"string"},"datatype":"string"},"type":"statement","id":"Q856879$B5D845D7-A5CE-4069-83AE-C091EAC2F8CD","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":"Q856879$8741FA9E-191A-4892-8169-3B444FCFEB2A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3825bafb54d6b98ddc3547811db5ca9d2f398b49","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.06.016","type":"string"},"datatype":"url"},"type":"statement","id":"Q856879$9B088183-57D2-49F1-AB81-6AE4597359C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15afa7d4d53715a366620c7467d17825904f27f9","datavalue":{"value":"W2051902598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$97D6FFFD-8B05-4176-991C-5B8C58E3FA70","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b250605762d13c03d617aa20d4983a5f6175be3b","datavalue":{"value":{"entity-type":"item","numeric-id":1972146,"id":"Q1972146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$29AF14B7-111C-4999-BED8-9DA92DAD660B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf54124463b6acc3ddfd64d5fc06b3f4ec6deb7a","datavalue":{"value":{"entity-type":"item","numeric-id":4713098,"id":"Q4713098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$358C8D33-2E90-424F-968B-4E2B8C464AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d14491f6053c28ca45662edbd3c335ca6a1febe","datavalue":{"value":{"entity-type":"item","numeric-id":4330733,"id":"Q4330733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$96F4DAC2-0B55-4E79-9344-AFB1BB72318F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e60802045a10baa263214902df900a40494a6163","datavalue":{"value":{"entity-type":"item","numeric-id":5589124,"id":"Q5589124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$B4F2D181-8C16-4EE2-86CA-ABFA674CFC22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8ecad97d1dd361fbfa65c931f2f8b5b385b1b46","datavalue":{"value":{"entity-type":"item","numeric-id":4262235,"id":"Q4262235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$B9A407E9-3DB1-43BD-8FE8-29191472FF67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c527c582d3fa1a6c978424e1548045adca0f89df","datavalue":{"value":{"entity-type":"item","numeric-id":1363661,"id":"Q1363661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q856879$D1CDF218-CDB1-41AD-AE6C-EABE08D0252F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8bf65a8e162efdf0c2a2fff7a4cb345276cae87e","datavalue":{"value":"10.1016/J.DISC.2006.06.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q856879$F3CFFBB2-634D-49B4-94BA-10A4B1080B3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36eb8d8472883a79a845ffa61992948b989b95fc","datavalue":{"value":{"entity-type":"item","numeric-id":5492650,"id":"Q5492650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d67788333c900d0424bde1713e19ac6eca30507","datavalue":{"value":{"amount":"+0.90692246","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":"Q856879$54C94519-5606-44D3-86AB-290DC3DCB7C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20ae0c3a5ffd45189b53d506f6491e96e63eb1ec","datavalue":{"value":{"entity-type":"item","numeric-id":5403021,"id":"Q5403021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e088d66ff57041fdb3d81c57eebdef8b6540810","datavalue":{"value":{"amount":"+0.90539896","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":"Q856879$160666E0-1AEC-4364-B62A-1B3D31431E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6388ebb1e539961c638427e639b83d37186e3eae","datavalue":{"value":{"entity-type":"item","numeric-id":2389459,"id":"Q2389459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ea5f667ab1f6beee93774a6cac9c527fe874bba","datavalue":{"value":{"amount":"+0.8991248","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":"Q856879$32A965C2-0DC0-47BD-AB78-DFCF3EF943CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"552fee2c91e30313457f146612c3e4ae8a5c9d3c","datavalue":{"value":{"entity-type":"item","numeric-id":1692641,"id":"Q1692641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84b1e8826c914467a8b5818baa0a94bf340ad9ce","datavalue":{"value":{"amount":"+0.8965528","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":"Q856879$A444BE7B-FE1F-4537-B56D-92906FB9D3CF","rank":"normal"},{"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":"3d0042204a6d7b8e6ae77d7e2926c75fb9faae83","datavalue":{"value":{"amount":"+0.88643056","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":"Q856879$D442433E-ADA2-4811-8E8C-AF264C8823A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a5c8ad3472a639c8c572eaeabf720df99b56e6c","datavalue":{"value":{"entity-type":"item","numeric-id":5016351,"id":"Q5016351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63cfd03447c3cc570a6e4b1c74955ebd79958ef2","datavalue":{"value":{"amount":"+0.88439155","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":"Q856879$61D64B39-B4A7-4310-9F3F-66417C2DD3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f2086fc9220dc2ab4708ebb9753bfb230401edd","datavalue":{"value":{"entity-type":"item","numeric-id":1284483,"id":"Q1284483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"735920ebc18c477336d0aa6b3faafb8af8d1ae1b","datavalue":{"value":{"amount":"+0.8830724","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":"Q856879$49B1B2DF-EBDF-4CD8-8710-DDEBC00CA918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd9d5081d21d8bdbbddd899900b86ede9d1058dc","datavalue":{"value":{"entity-type":"item","numeric-id":5691420,"id":"Q5691420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a8ec5e2e4d571247bb6672fef11d45ab7fa8a09","datavalue":{"value":{"amount":"+0.88210064","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":"Q856879$5A59380B-F0E9-41A7-BACA-285102384E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b0053a1dc0aac6341973c512fd2b08c2af7b0e7","datavalue":{"value":{"entity-type":"item","numeric-id":2182187,"id":"Q2182187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44ace1d1e350135ba27a6c33b9ee46aff3409344","datavalue":{"value":{"amount":"+0.8793782","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":"Q856879$C4F394CC-FAB6-43EF-92AA-61283C5DBA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a52d3c020ea4902062f7b16d8c701d83964f37b7","datavalue":{"value":{"entity-type":"item","numeric-id":2409751,"id":"Q2409751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93357f5637e99605813263e629f771c8a3cbb188","datavalue":{"value":{"amount":"+0.87924564","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":"Q856879$7D46E703-9D76-4EBF-9D5D-3609809E0432","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:856879","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:856879"}}}}}