## Abstract

Let B(G) denote the bandwidth of graph G. For any tree T, V_{e}(T) denote the set of leaves (vertices of degree 1) 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 another tree with the same number of leaves, and for this latter tree, the bound in the above inequality is reached. In other words, the bound is reached in almost all trees. We also describe trees S_{r,d}, where d and r are integers and ∥Ve(S_{r,d})∥=(d+1)×d^{r_1}. Moreover, we will show that if d (≤2r) is large, the ratio of the bandwidth to the number of leaves of S_{r,d} will be very small.

Original language | English |
---|---|

Pages (from-to) | 193-196 |

Number of pages | 4 |

Journal | Acta Mathematicae Applicatae Sinica |

Volume | 14 |

Issue number | 2 |

DOIs | |

Publication status | Published - Apr 1998 |

Externally published | Yes |

## Scopus Subject Areas

- Applied Mathematics

## User-Defined Keywords

- Bandwidth
- Leaves
- Tree