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.

We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly

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.

Akhmedov, A. and Shreve, W. (2014) Balance in Random Trees.

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

[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