Balance in Random Trees
Abstract: We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly k-balanced for any k ≥ 3. Definition: Color the vertices of graph G with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. G is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.
Cite this paper: Akhmedov, A. and Shreve, W. (2014) Balance in Random Trees. Open Journal of Discrete Mathematics, 4, 97-108. doi: 10.4236/ojdm.2014.44013.
References

[1]   Lee, S.-M., Liu, A. and Tan, S.K. (1992) On Balanced Graphs. Congressus Numerantium, 87, 59-64.

[2]   Cahit, I. (1987) Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs, Ars Combinatoria, 23, 201-207.

[3]   Gallian, J.A. (2009) A Dynamical Survey of Graph Labeling. The Electronics Journal of Combinatorics, Dynamic Survey 6, 43 p. (electronic).

[4]   Graham, R. and Sloane, N. (2009) On Additive Bases and Harmonious Graphs. SIAM Journal of Algebraic and Discrete Mathematics, 1, x382-x404.
http://dx.doi.org/10.1137/0601045

[5]   Cahit, I. (1990) On Cordial and 3-Equitable Graphs, Utilitas Mathematica, 37, 189-198.

[6]   Cayley, A. (1889) A Theorem on Trees. The Quarterly Journal of Mathematics, 23, 376-378.

[7]   West, D.B. (2001) Introduction to Graph Theory. 2nd Edition, Prentice-Hall, Inc., Upper Saddle River, 82-83.

[8]   Otter, R. (1948) The Number of Trees. Annals of Mathematics, 49, 583-599.

[9]   Bollobás, B. and Guy, R. (1983) Equitable and Proportional Coloring of Trees. Journal of Combinatorial Theory, Series B, 34, 177-186.

[10]   Ben-Eliezer, I. and Krivelevich, M. (2009) Perfectly Balanced Partitions of Smoothed Graphs. Electronic Journal of Combinatorics, 16, Note N14.

[11]   Bollobás, B. (2001) Random Graphs. Cambridge Studies in Advanced Mathematics (Book 73). 2nd Edition, Cambridge University Press, Cambridge.

[12]   Goh, W. and Schmutz, E. (1994) Unlabeled Trees: Distribution of the Maximum Degree. Random Structures and Algorithms, 5, 13-24.

[13]   Kong, M.C., Lee, S.-M., Seah, E. and Tang, A. (2008) A Complete Characterization of Balanced Graphs (English Summary). Journal of Combinatorial Mathematics and Combinatorial Computing, 66, 225-236.

[14]   Moon, J.W. (1968) On the Maximum Degree in a Random Tree. The Michigan Mathematical Journal, 15, 429-432.

[15]   Rényi, A. (1959) Some Remarks on the Theory of Trees. Magyar Tud. Akad. Mat. Kutat Int. Kzl, 4, 73-85.

[16]   Meir, A. and Moon, J.W. (1968) On Nodes of Degree Two in Random Trees. Mathematika, 15, 188-192.
http://dx.doi.org/10.1112/S0025579300002552

[17]   Drmota, M. and Gittenberger, B. (1999) Distribution of Nodes of Given Degree in Random Trees. Journal of Graph Theory, 31, 227-253.
http://dx.doi.org/10.1002/(SICI)1097-0118(199907)31:3<227::AID-JGT6>3.0.CO;2-6

Top