{"entities":{"Q463048":{"pageid":464815,"ns":120,"title":"Item:Q463048","lastrevid":62013828,"modified":"2026-04-11T03:12:06Z","type":"item","id":"Q463048","labels":{"en":{"language":"en","value":"Graph homomorphisms between trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6360684"}},"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":"Q463048$A5B7BC4D-DA26-4CE0-B1AD-148E69811B55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa7fc2ae86af0cd8e304ea49f96bf391aac3f332","datavalue":{"value":{"text":"Graph homomorphisms between trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q463048$9F93A364-4A55-4D4B-93F1-D3E367F505A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31973bf14e14fd0b221cb84f694c986ea3058c05","datavalue":{"value":"1298.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$B7F2FE0A-4B0E-4364-8E0F-4FCC055F18AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ba32d32bb779f623048f513cf2e42c655f233b9","datavalue":{"value":{"entity-type":"item","numeric-id":412252,"id":"Q412252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$C7560EB0-FB7C-459D-BAC2-0B240F95C73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f3eca0f02d026e6e1fc9bfe37fe5b2571a93125","datavalue":{"value":{"entity-type":"item","numeric-id":311508,"id":"Q311508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$4A503268-10A6-4612-B818-418620D2E41B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$81016073-343A-4369-A9ED-981BF5C777DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19223fa13371e3ce1b1dd08c8b63557fc81ef3f8","datavalue":{"value":{"time":"+2014-10-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q463048$83913092-4FF4-4022-9FB9-76599644FC7A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"53e9a3a9caebe2b62557655f410c86bcd1fe228d","datavalue":{"value":"https://arxiv.org/abs/1307.6721","type":"string"},"datatype":"url"},"type":"statement","id":"Q463048$1F1EFD90-1D08-407E-A832-9A4EFA7D8F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"84741515e064626fa4d26c6cdfc2fbe87170e27f","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p9","type":"string"},"datatype":"url"},"type":"statement","id":"Q463048$F2709820-F94B-4C76-9B4D-C36B898E06BD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d72238af6c99bef33109a5e1a8df564694a92c4d","datavalue":{"value":"Summary: In this paper we study several problems concerning the number of~homomorphisms of trees. We begin with an algorithm for the number of homomorphisms~from a tree to any graph. By using this~algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of Bollob\u00e1s and Tyomkyn's result concerning the number of walks in trees.{  }Some other main results of the paper are the following. Denote by \\(\\mathrm{hom}(H,G)\\) the number of homomorphisms from a graph \\(H\\) to a graph \\(G\\). For any tree \\(T_m\\) on \\(m\\) vertices we give a general lower bound for \\(\\mathrm{hom}(T_m,G)\\) by certain entropies of Markov chains defined on the graph \\(G\\). As a particular case, we show that for any graph \\(G\\),  \\[ \\exp(H_\\lambda(G))\\lambda^{m-1}\\leqslant\\mathrm{hom}(T_m,G), \\]  where \\(\\lambda\\) is the largest eigenvalue of the adjacency matrix of \\(G\\) and \\(H_\\lambda(G)\\) is a certain constant depending only on \\(G\\) which we call the~spectral entropy of \\(G\\). We also show that if \\(T_m\\) is any fixed tree and  \\[ \\mathrm{hom}(T_m,P_n)>\\mathrm{hom}(T_m,T_n), \\]  for some tree \\(T_n\\) on \\(n\\) vertices, then \\(T_n\\) must be the tree obtained from a path \\(P_{n-1}\\) by attaching a pendant vertex to the second vertex of \\(P_{n-1}\\).{  }All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$EE9B4DBC-0E8A-4E0C-840C-AE20C1BAC888","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$BCFF64B0-6F97-49C9-967D-2E99443B4B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$BF8ED1F2-BE27-46EB-8ABD-8BEB2211889D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$E7AA8624-8F69-4721-8ABE-EB7AF11704D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e69bea0119b72b8a594d43ad60a010cb94aeda4a","datavalue":{"value":"6360684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$225C2614-E44B-4DAD-9C29-326261FD44CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$B3AD59C7-6AB8-4E08-A061-278CA65BC99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcef69667e3e554fa7924e648dc86649eaec2210","datavalue":{"value":"walks","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$891162A0-DD12-4C35-ABEF-DA402E081042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2eb968c30f93efc86855751168fe668900e5112c","datavalue":{"value":"graph homomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$0569B598-2422-4A60-885E-2C5987BBB6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$02DB1F65-AF91-495D-97E1-8AEFA979DC10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191403835f9d573ead779b7e37a9e1db540852cc","datavalue":{"value":"extremal problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$4CE277C8-C5CF-4C17-B26F-A24C4E9D180D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c798d8e721bdd220a954ade8a00bf15138c802a","datavalue":{"value":"KC-transformation","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$80E41041-D523-49E0-A5E0-8AC0EEBF9FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54386443767439a4565bd3fedc3d37d2c4a4f85d","datavalue":{"value":"Markov chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q463048$79B02C2F-FAB1-4094-86A3-A9E81EA16E7A","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":"Q463048$BDAF6891-B767-4AF6-B8E6-EBDFF18960BF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e957a811195d68ba86550a1124c6541e2d81d5f1","datavalue":{"value":{"entity-type":"item","numeric-id":1045039,"id":"Q1045039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$CD3664F3-F341-4E7C-AA38-C9166A741A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$071FEE65-CEDF-4391-A841-2F1D3CABFF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"879e09ea9474957555726ef5b4f6755b267f0f50","datavalue":{"value":{"entity-type":"item","numeric-id":2888879,"id":"Q2888879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$D0520309-05BF-4930-9F4D-5EEC16D10202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$48DA97BD-4B8F-4C1F-91A3-B37FB037A4AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$19C0B50C-369E-4218-92A1-671C8642EBA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9c33ebc6b9acea203c97979ed7cfc76290093b","datavalue":{"value":{"entity-type":"item","numeric-id":532127,"id":"Q532127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$1CFD3154-C06C-4B11-8C4C-0004BDCBE104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf42effaa99703dbd576ff415e18804d7c5442a8","datavalue":{"value":{"entity-type":"item","numeric-id":2852613,"id":"Q2852613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$0836ECAA-645F-4F0E-8B92-81E19CA360D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0cf77af371445c4022c8a951e5fc07a382d8eb4","datavalue":{"value":{"entity-type":"item","numeric-id":463048,"id":"Q463048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$7FE9B266-49E2-4668-90FE-2FFEA8D22553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca855deddc63408e4e32740660493921f7b6bd47","datavalue":{"value":{"entity-type":"item","numeric-id":353399,"id":"Q353399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$BB3FD996-055A-478C-8AC1-8970A3770A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3cb03db1d300473687697da5854b1bf6c6bfd42","datavalue":{"value":{"entity-type":"item","numeric-id":1025536,"id":"Q1025536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$ED765B87-D1EA-4A51-BD1B-F7D69C0C9D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d40f2f04b935b631f95743345d7e56e03691f1","datavalue":{"value":{"entity-type":"item","numeric-id":1912755,"id":"Q1912755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$F569F9DE-085B-407C-AAF5-BEB991E3A9CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee680a867777fc4cc9b818b2a4b1c24966e1c2b4","datavalue":{"value":{"entity-type":"item","numeric-id":3968971,"id":"Q3968971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$31DDAA74-E363-4D90-A1EC-23DFB134C2C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887591d82ea19e5112e35fc836d825033f8f28f9","datavalue":{"value":{"entity-type":"item","numeric-id":648968,"id":"Q648968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$1A7487D9-B5E6-4CF5-A511-CC071B966277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eb398653dc06d5e5734d605b37b20ff60f8ced5","datavalue":{"value":{"entity-type":"item","numeric-id":3834062,"id":"Q3834062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$CEF6443C-4A42-4337-B4B5-B6FF2D5D84F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5163eec77c65afeed40498020a10ad87b467874f","datavalue":{"value":{"entity-type":"item","numeric-id":409484,"id":"Q409484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$562B168C-CF05-49F1-8A8D-03BA8883CDE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd4d909aac04d31f54bf12aa403c4abc8d208a72","datavalue":{"value":{"entity-type":"item","numeric-id":2555861,"id":"Q2555861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$2EE2DFED-B2DB-4040-BE58-2AE5E8625FC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1758d7b3bd2c41aa3b42e01008f4d1d8dae2d14d","datavalue":{"value":{"entity-type":"item","numeric-id":2366960,"id":"Q2366960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$3C9EFF49-888F-4FF2-9AEE-2D317AA85A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2213ae3aa64294e5f59b3f8d80dc48f28b09fcb4","datavalue":{"value":{"entity-type":"item","numeric-id":1332414,"id":"Q1332414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$4EF22E69-539F-4872-81F7-BD51D3439106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d825095afe6e2215dbc5ab36153017eec07800e3","datavalue":{"value":{"entity-type":"item","numeric-id":4344108,"id":"Q4344108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q463048$5BA17AF3-57B6-4E4D-9B85-0AB9B42A879E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fb04b50d335e91a3aa828cdc71dd9ca4e759629a","datavalue":{"value":"bafkreihtjd4o4u4mmdzwrtfv6ngvth5jtignlmsjogptdp7b2wprpnf4wy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q463048$1FD441DC-F8C8-4A54-A20D-5CA2A6F8A403","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58b3cf2494e14c815980d0a453f8b7267c670320","datavalue":{"value":{"entity-type":"item","numeric-id":5502101,"id":"Q5502101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"421b5f92b99f42ebb8325f08e5b6ffa5a8e97cee","datavalue":{"value":{"amount":"+0.8491631150245667","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":"Q463048$0F16B877-A574-4EA7-BB7C-B558FF068B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e05029f28240ef64819e99c7c176ab86065e4c9","datavalue":{"value":{"entity-type":"item","numeric-id":5199417,"id":"Q5199417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7fe39b071bc789f3a30cf713424c686f7655b74","datavalue":{"value":{"amount":"+0.7499279379844666","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":"Q463048$D3A2B1D7-FA37-46E6-A741-EFBBE171A96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3857ef1421bfd1b65896c204a443eb0f5789b34","datavalue":{"value":{"entity-type":"item","numeric-id":2441343,"id":"Q2441343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2429f2fe4bffed1106069d1085c1d0e870293649","datavalue":{"value":{"amount":"+0.7437556385993958","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":"Q463048$753C8DF6-5631-40D2-8557-83C5BBC8AE5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d3d6d41bb909159493a08eb214ff32cc364f5ba","datavalue":{"value":{"entity-type":"item","numeric-id":3057061,"id":"Q3057061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fb88f1c5cdd08a033c4be259e789524e7397fc9","datavalue":{"value":{"amount":"+0.7379810214042664","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":"Q463048$8E536237-4BD8-476D-9BC6-E01A8592666E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da6a98280ff54b5023247492b6017d2d4af4647f","datavalue":{"value":{"entity-type":"item","numeric-id":5696361,"id":"Q5696361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5c84bbc50653a0f77175f129baf8ade268982b3","datavalue":{"value":{"amount":"+0.7240265607833862","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":"Q463048$49E0736A-60C0-462B-B471-DB871C04650D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph homomorphisms between trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_homomorphisms_between_trees"}}}}}