The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
type: Item
instance of: scholarly article
title: The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
zbMATH Open document ID: 0856.05090
DOI: 10.1016/0012-365X(96)00205-1
author: Kiyoshi Ando
author: Atsushi Kaneko
author: Severino V. Gervacio
published in: Discrete Mathematics
publication date: 1997-02-17T00:00:00Z
review text: The bandwidth of a graph \(G = (V,E)\) is the minimum over all bijective functions \(f : B \to \{1, 2, \dots, |V |\}\), of \(\max \{|f(v) - f(w) |: \{v,w\} \in E\}\). This paper shows that a tree with \(k\) leaves has bandwidth at most \(\lceil k/2 \rceil\).
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 896017
zbMATH Keywords: bandwidth
zbMATH Keywords: tree
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q4039999
cites work: A remark on a problem of Harary
full work available at URL: 0012-365x(96)00205-1
OpenAlex ID: W2088019809
Recommended article: Bandwidth of the complete \(k\)-ary tree
Recommended article: Q3731640
Recommended article: The bandwidth of the complement of a \(k\)-tree
Recommended article: On upper bounds of bandwidths of trees
Recommended article: On number of leaves and bandwidth of trees
Recommended article: Bandwidth of trees of diameter at most 4
Recommended article: Q4390632
Recommended article: On the Cutwidth and the Topological Bandwidth of a Tree
Recommended article: Q3325746
Recommended article: Q4863471
description: scientific article; zbMATH DE number 896017