Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-08T14:34:21.820Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost Every Tree With m Edges Decomposes K2m,2m

Published online by Cambridge University Press:  03 December 2013

M. DRMOTA  and
A. LLADÓ
M. DRMOTA
Affiliation:
Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Vienna, Austria (e-mail: michael.drmota@tuwien.ac.at
A. LLADÓ
Affiliation:
Departament de Matemàtica Aplicada~IV, Universitat Politècnica de Catalunya–BarcelonaTech, Barcelona, Spain (e-mail: allado@ma4.upc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K2m,2m, a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O(m2) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size.

Keywords

Primary 05C51Secondary 05C80

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 50 - 65
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. (1999) Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 7–29.CrossRefGoogle Scholar
[2]Alon, N. (2000) Additive Latin transversals. Israel J. Math. 117 125–130.Google Scholar
[3]Càmara, M., Lladó, A. and Moragas, J. (2009) On a conjecture of Graham and Häggkvist with the polynomial method. Europ. J. Combin. 30 1585–1592.Google Scholar
[4]Dasgupta, S., Károlyi, G., Serra, O. and Szegedy, B. (2001) Transversals of additive Latin squares. Israel J. Math. 126 17–28.Google Scholar
[5]Drmota, M. (2009) Random Trees, Springer.CrossRefGoogle Scholar
[6]Drmota, M. and Gittenberger, B. (1999) The distribution of nodes of given degree in random trees. J. Graph Theory 31 227–253.3.0.CO;2-6>CrossRefGoogle Scholar
[7]Drmota, M. and Gittenberger, B. (2010) The shape of unlabeled rooted random trees. Europ. J. Combin. 31 2028–2063.CrossRefGoogle Scholar
[8]Flajolet, P. and Odlyzko, A. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.CrossRefGoogle Scholar
[9]Gallian, J. A. (2007) A dynamic survey of graph labeling. Electron. J. Combin. 5 #DS6.Google Scholar
[10]Häggkvist, R. L. (1989) Decompositions of complete bipartite graphs. In Surveys in Combinatorics (Siemons, J., ed.), Cambridge University Press, pp. 115–146.Google Scholar
[11]Hwang, H. K. (1994) Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques. PhD thesis, Ecole Polytechnique, New York.Google Scholar
[12]Kézdy, A. E. (2006) ρ-valuations for some stunted trees. Discrete Math. 306 2786–2789.Google Scholar
[13]Kézdy, A. E. and Snevily, H. S. (2002) Distinct sums modulo n and tree embeddings. Combin. Probab. Comput. 11 35–42.CrossRefGoogle Scholar
[14]Lladó, A. and López, S. C. (2005) Edge-decompositions of Kn,n into isomorphic copies of a given tree. J. Graph Theory 48 1–18.Google Scholar
[15]Lladó, A., López, S. C. and Moragas, J. (2010) Every tree is a large subtree of a tree that decomposes Kn or Kn,n. Discrete Math. 310 838–842.Google Scholar
[16]Otter, R. (1948) The number of trees. Ann. of Math. (2) 49 583–599.Google Scholar
[17]Ringel, G. (1964) Problem 25. In Theory of Graphs and its Applications, Nakl. CSAV, Praha, p. 162.Google Scholar
[18]Robinson, R. W. and Schwenk, A. J. (1975) The distribution of degrees in a large random tree. Discrete Math. 12 359–372.CrossRefGoogle Scholar
[19]Snevily, H. (1997) New families of graphs that have α-labelings. Discrete Math. 170 185–194.CrossRefGoogle Scholar
[20]Yuster, R. (2000) Packing and decomposition of graphs with trees. J. Combin. Theory Ser. B 78 123–140.CrossRefGoogle Scholar