跳至主要内容

Balance in Random Trees

Read full paper at:
http://www.scirp.org/journal/PaperInformation.aspx?PaperID=50292#.VDSRfVfHRK0

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. 
 

[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                                              eww141008lx
标签：

评论

发表评论

此博客中的热门博文

A Comparison of Methods Used to Determine the Oleic/Linoleic Acid Ratio in Cultivated Peanut (Arachis hypogaea L.)

Cultivated peanut ( Arachis hypogaea L.) is an important oil and food crop. It is also a cheap source of protein, a good source of essential vitamins and minerals, and a component of many food products. The fatty acid composition of peanuts has become increasingly important with the realization that oleic acid content significantly affects the development of rancidity. And oil content of peanuts significantly affects flavor and shelf-life. Early generation screening of breeding lines for high oleic acid content greatly increases the efficiency of developing new peanut varieties. The objective of this study was to compare the accuracy of methods used to classify individual peanut seed as high oleic or not high oleic. Three hundred and seventy-four (374) seeds, spanning twenty-three (23) genotypes varying in oil composition (i.e. high oleic (H) or normal/not high oleic (NH) inclusive of all four peanut market-types (runner, Spanish, Valencia and Virginia), were individually tested ...
发表评论
阅读全文

Location Optimization of a Coal Power Plant to Balance Costs against Plant’s Emission Exposure

Fuel and its delivery cost comprise the biggest expense in coal power plant operations. Delivery of electricity from generation to consumers requires investment in power lines and transmission grids. Placing a coal power plant or multiple power plants near dense population centers can lower transmission costs. If a coalmine is nearby, transportation costs can also be reduced. However, emissions from coal plants play a key role in worsening health crises in many countries. And coal upon combustion produces CO 2 , SO 2 , NO x , CO, Metallic and Particle Matter (PM10 & PM2.5). The presence of these chemical compounds in the atmosphere in close vicinity to humans, livestock, and agriculture carries detrimental health consequences. The goal of the research was to develop a methodology to minimize the public’s exposure to harmful emissions from coal power plants while maintaining minimal operational costs related to electric distribution losses and coal logistics. The objective was...
发表评论
阅读全文

Evaluation of the Safety and Efficacy of Continuous Use of a Home-Use High-Frequency Facial Treatment Appliance

At present, many home-use beauty devices are available in the market. In particular, many products developed for facial treatment use light, e.g., a flash lamp or a light-emitting diode (LED). In this study, the safety of 4 weeks’ continuous use of NEWA TM , a high-frequency facial treatment appliance, every alternate day at home was verified, and its efficacy was evaluated in Japanese individuals with healthy skin aged 30 years or older who complained of sagging of the facial skin.  Transepidermal water loss (TEWL), melanin levels, erythema levels, sebum secretion levels, skin color changes and wrinkle improvement in the facial skin were measured before the appliance began to be used (study baseline), at 2 and 4 weeks after it had begun to be used, and at 2 weeks after completion of the 4-week treatment period (6 weeks from the study baseline). In addition, data obtained by subjective evaluation by the subjects themselves on a visual analog scale (VAS) were also analyzed. Fur...
发表评论
阅读全文