{"entities":{"Q353399":{"pageid":355166,"ns":120,"title":"Item:Q353399","lastrevid":61185390,"modified":"2026-04-10T21:43:07Z","type":"item","id":"Q353399","labels":{"en":{"language":"en","value":"Tree-minimal graphs are almost regular"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6187613"}},"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":"Q353399$FE994EED-5250-4B38-B643-5B0CFC0FB982","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"89b8f77908badbea1385143a1b4f7cd598986bcb","datavalue":{"value":{"text":"Tree-minimal graphs are almost regular","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q353399$309F01F9-6BB3-4726-AA5F-6C17F6AA742E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"241233d1913ffe80e59e9ec313d1a93600afc4b6","datavalue":{"value":"1272.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$1BE2EE06-B38F-4DE5-ADD4-E7F6DAA7455B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"63b25dd4191d75861d8dbf96d1a8be0234dbf724","datavalue":{"value":{"entity-type":"item","numeric-id":285060,"id":"Q285060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$01EABC09-E9D5-4925-9F02-94B1F8B204FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef9f22506a0bcbf1151d6523fea2bf6c3ee4e900","datavalue":{"value":{"entity-type":"item","numeric-id":353398,"id":"Q353398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$45E0324C-1F48-4F2C-98E4-857BB88D18D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93a3904bbec182d67e761f38904a81bb2531b67d","datavalue":{"value":{"entity-type":"item","numeric-id":178704,"id":"Q178704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$E8341AC7-0F5A-4DBB-A96E-94A207AC790E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b2dc7fb86714f67c87c73e07c13ee1e0d7b9d71","datavalue":{"value":{"entity-type":"item","numeric-id":168649,"id":"Q168649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$90032E1E-8F7E-40B5-9915-138E97F5C94B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"32c25fa8e627a607462b66f5901b2fab775a3c7c","datavalue":{"value":{"entity-type":"item","numeric-id":190558,"id":"Q190558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$451AC30A-F8C4-433F-8A9B-CF42B3A174F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2532270aa021c282902fb16beb1092e301044e83","datavalue":{"value":{"entity-type":"item","numeric-id":290807,"id":"Q290807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$79C5D02C-C96D-41A9-BFC9-DCFB11E650B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$2558E11F-395E-4DDD-A8A4-F99E4DCAC626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"593083695f46fe82f0f9df972be5bb5705c615f8","datavalue":{"value":{"entity-type":"item","numeric-id":273185,"id":"Q273185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$808180C7-7597-4469-A521-E841EF18EE39","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6b8b858ece76e2bb88c236d487f13fce9f1e9789","datavalue":{"value":{"entity-type":"item","numeric-id":247199,"id":"Q247199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$106892D9-37BE-47F3-9D15-120D3152A0AD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7648b60b59954b2d001592c2d3cc73e7f7fb262d","datavalue":{"value":{"time":"+2013-07-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q353399$271526B4-0DAF-4A36-A909-BC9E8919F01D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q353399$EF974E6E-7614-47F5-BB21-BF97A5144B1E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$45F026D1-32E6-4F36-848B-46E0BB1F1C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$936964A6-8D28-4579-B2D7-2F9D68E0D40E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$400C3F4D-9361-4AED-B7A5-1DCFABA6E848","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6618235247d6481823e254cd0dfb498a903b6667","datavalue":{"value":"6187613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$1FA12A49-85B6-41D0-87B2-3C20D349A4B4","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":"Q353399$489AE7D3-560B-40D5-B507-19D71B2D54F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82046b428ca65078d872df1ae1149dd72a5c5f26","datavalue":{"value":"https://doi.org/10.4310/joc.2012.v3.n1.a2","type":"string"},"datatype":"url"},"type":"statement","id":"Q353399$6A6A3AC8-57B5-4556-AE8C-5BEBDE31FCBE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5913c7dc313a90f83ec8039e74ba2dad5b7de41e","datavalue":{"value":"W2312696900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$1843A3E4-68A1-432C-8758-61D964CBEF83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"90becd4d5a70670ffa51b5a5e04acf853c98199a","datavalue":{"value":"10.4310/JOC.2012.V3.N1.A2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q353399$54CA3EBF-1BE7-4E63-9501-B63CD14DB3DE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"130d0ac71527914cc231c1f6ea308988d23f303a","datavalue":{"value":{"entity-type":"item","numeric-id":311564,"id":"Q311564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47a56eed92bc90128a0b269f651c27183311e7b8","datavalue":{"value":{"amount":"+0.85711026","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$E1C36682-C776-424F-9088-CE10751BB088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ad38ca371f82b319e6fc84eb6eeba90809871ea","datavalue":{"value":{"entity-type":"item","numeric-id":2712588,"id":"Q2712588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b2139f922e35e688192772ed2d3f24f3243167f","datavalue":{"value":{"amount":"+0.7874947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$E94E1FEA-90BD-40B8-AE42-C28C578A3D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5470fb65f55b4e3b8d6cc6e618f6d464418d4a0b","datavalue":{"value":{"entity-type":"item","numeric-id":735124,"id":"Q735124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"451d6461944314acdf459b891c02603133f538e5","datavalue":{"value":{"amount":"+0.780376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$C0B55809-01BE-40B2-AA07-057015E93EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46ea093bbff6a9a601321f55f7ba3db69c4d1fca","datavalue":{"value":{"entity-type":"item","numeric-id":4161354,"id":"Q4161354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44aa239c784843c2d7ab1532f357a91f31bfe1b5","datavalue":{"value":{"amount":"+0.7743608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$FE26086E-C2EF-489C-9E04-585BF0391D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ef1491c6f4103ab497605df6d00cc4586611849","datavalue":{"value":{"entity-type":"item","numeric-id":1767620,"id":"Q1767620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f722ba4bca5be237babe7c51b2ac4d91ce5b1e2","datavalue":{"value":{"amount":"+0.76213515","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$4E4B594D-09A6-4F4C-8124-D78D4D6CB4EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eb391a9ed77a411580f09f8bf067b85a9f04baa","datavalue":{"value":{"entity-type":"item","numeric-id":1613484,"id":"Q1613484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5015cabd13fda4d412a048b108ef8ca94a764fb7","datavalue":{"value":{"amount":"+0.759805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$D5028DA3-39ED-4CA2-8BAC-1281D54AAAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31bcd074cd19db9b17a6345eb13ccf472ea3ca1a","datavalue":{"value":{"entity-type":"item","numeric-id":3460512,"id":"Q3460512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d2323e2f74dcad615c5f8358b55bf81de970aa","datavalue":{"value":{"amount":"+0.75811887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$6DEC26DE-91C8-466E-BC15-6CEAFDF8F065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06e1f3db83ee91fe2232c41664740df762f6de6a","datavalue":{"value":{"entity-type":"item","numeric-id":2181915,"id":"Q2181915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cea686eadd9047b84a72e5a2dd5655cf0dd79724","datavalue":{"value":{"amount":"+0.7539368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$C8F4EDDF-66DF-429E-961C-939DB07528C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb1f0a48cbf4b38a4c6c15caa0e303bec6ac66e","datavalue":{"value":{"entity-type":"item","numeric-id":3605159,"id":"Q3605159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c6a80598fe10a76452d0dcb36b5d2412f111b2c","datavalue":{"value":{"amount":"+0.7512114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q353399$6FFB9392-53C1-4A50-8E77-2E635833BC1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41ad1bca7764d5244229985586a28152f59779d7","datavalue":{"value":"\\(N_F(G)\\) denotes the number of labelled copies of a subgraph \\(F\\) in a graph \\(G\\); \\(d_v\\) denotes the degree of vertex \\(v\\). Addressing a problem of [\\textit{J. Skokan} and \\textit{L. Thoma}, Graphs Comb. 20, No. 2, 255--262 (2004; Zbl 1054.05091)], the authors prove NEWLINENEWLINENEWLINE NEWLINETheorem 1. For all \\(\\varepsilon\\in(0,1]\\) and all integers \\(t\\geq3\\), there exists \\(\\delta>0\\) so that, whenever \\(p \\gg n^{-\\frac1{t-2}}\\), the following statement holds: Let \\(T\\) be a tree with \\(t\\) vertices, and let \\(G=(V,E)\\) be a graph with \\(n\\) vertices and \\(|E|=p{n\\choose2}\\) edges. If \\(N_T(G)\\leq(1+\\delta)p^{t-1}n^t\\), then \\(\\sum_{v\\in V}\\left|d_v-d\\right|<\\varepsilon pn^2\\). NEWLINENEWLINENEWLINE NEWLINEFor a tree \\(T\\), \\(\\hat N_T(G)\\) denotes the number of edge-preserving maps \\(h : V(T) \\to V(G)\\). Theorem 1 is a consequence of the following theorem, ``which extends a result of [\\textit{N. Alon, S. Hoory} and \\textit{N. Linial}, Graphs Comb. 18, No. 1, 53--57 (2002; Zbl 0990.05075)] from paths to arbitrary trees'': NEWLINENEWLINENEWLINE NEWLINETheorem 3. Let \\(T\\) be a tree with \\(t\\geq3\\) vertices, and let \\(G = (V,E)\\) be a graph with \\(n\\) vertices and average degree \\(d\\). Then \\(\\hat N_T(G) \\geq nd\\prod_{v\\in V} d_v^{\\frac{(t-2)d_v}{nd}}\\). NEWLINENEWLINENEWLINE NEWLINEIt is also shown that the proof of Theorem 3 can be altered to prove NEWLINENEWLINENEWLINE NEWLINETheorem 5. Let \\(P_3\\) denote the path with 3 edges, and let \\(G\\) be a graph with \\(n\\) vertices, average degree \\(d\\), and minimum degree at least 3. Then \\(N_{P_3}(G)\\geq nd\\prod_{v\\in V}\\left(d_v-2\\right)^{\\frac{2d_v}{nd}}\\). NEWLINENEWLINENEWLINE NEWLINEThe authors thank Jacques Verstra\u00ebte for pointing out the relation of their work to [\\textit{P. Erd\u0151s} and \\textit{M. Simonovits}, Combinatorica 2, 275--288 (1982; Zbl 0508.05043)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q353399$D9B62510-5310-4ACF-BC9B-C917CE3BEC94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tree-minimal graphs are almost regular","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tree-minimal_graphs_are_almost_regular"}}}}}