On upper bounds of bandwidths of trees

DOI10.1007/BF02013150MaRDI QIDQ1899015zbMATH OpenFDO

Authors Bing Yao, Jianfang Wang

Publication date 26 February 1996

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02013150

zbMATH Keywords

bandwidthboundpathsstarstree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

This paper shows that the bandwidth of a tree with \(k\) leaves is at most \(\left\lfloor{k+ 1\over 2}\right\rfloor\). This bound is sharp for stars and paths.

Cites work

• Complexity Results for Bandwidth Minimization
• Graph theory with applications
• Graphs with small bandwidth and cutwidth
• The bandwidth problem for graphs and matrices—a survey

Cited in

(5)

• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
• scientific article; zbMATH DE number 3857138 (Why is no real title available?)
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• scientific article; zbMATH DE number 1445378 (Why is no real title available?)
• Some results on spanning trees

This page was built for publication: On upper bounds of bandwidths of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899015)