On number of leaves and bandwidth of trees

Peter Che Bor Lam*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


Let B(G) denote the bandwidth of graph G. For any tree T, Ve(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 Sr,d, where d and r are integers and ∥Ve(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 Sr,d will be very small.

Original languageEnglish
Pages (from-to)193-196
Number of pages4
JournalActa Mathematicae Applicatae Sinica
Issue number2
Publication statusPublished - Apr 1998
Externally publishedYes

Scopus Subject Areas

  • Applied Mathematics

User-Defined Keywords

  • Bandwidth
  • Leaves
  • Tree


Dive into the research topics of 'On number of leaves and bandwidth of trees'. Together they form a unique fingerprint.

Cite this