On the edge independence number of a random $(n,n)$-tree
Bull. Korean Math. Soc. 1996 Vol. 33, No. 1, 119-126
J. H. Cho and Moo Ha Woo
Korea University and Korea University
Abstract : An $(n, n)$-tree is a connected, acyclic, bipartite graph with $n$ light and $n$ dark vertices. Uniform probability is assigned to the space, $\Gamma(n, n)$, of $(n, n)$-trees. In this paper, we apply Hall's theorem to determine bounds for the edgeindependence numbers for almost all $(n,n)$-trees in $\Gamma(n,n)$. Consequently, we find that for almost all $(n,n)$-trees the percentage of dark vertices in a maximum matching is at least.
Keywords : Independence Number, Probabilistic Method
MSC numbers : 05C80
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd