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.

Keywords

Share and Cite:

Akhmedov, A. and Shreve, W. (2014) Balance in Random Trees. Open Journal of Discrete Mathematics, 4, 97-108. doi: 10.4236/ojdm.2014.44013.

Conflicts of Interest

The authors declare no conflicts of interest.

 [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