摘要
Let B(G) denote the bandwidth of graph G. For any tree T, Ve(T) denote the set of leaves(venices of degree l) of T. Wang and Yao[5] obtained that for any tree T, B(T)≤ 「Ve(T) /2」and the bound is sharp. In this paper, we show that any tree may be imbedded into anothertree with the same number of leaves, and for this latter tree, the bound in the above inequalityis reached. In other words, the bound is reached in almost all trees. We also describe trees Sr,d,where d and r are integers and lIVe (Sr,d ) =(d+ 1) × dr- 1. Moreover, we will show that if d (≤2r)is large, the ratio of the bandwidth to the number of leaves of S..d will be very small.
Let B(G) denote the bandwidth of graph G. For any tree T, Ve(T) denote the set of leaves(venices of degree l) of T. Wang and Yao[5] obtained that for any tree T, B(T)≤ 「Ve(T) /2」and the bound is sharp. In this paper, we show that any tree may be imbedded into anothertree with the same number of leaves, and for this latter tree, the bound in the above inequalityis reached. In other words, the bound is reached in almost all trees. We also describe trees Sr,d,where d and r are integers and lIVe (Sr,d ) =(d+ 1) × dr- 1. Moreover, we will show that if d (≤2r)is large, the ratio of the bandwidth to the number of leaves of S..d will be very small.
