On the problem of bandsize
type: Item
instance of: scholarly article
title: On the problem of bandsize
zbMATH Open document ID: 0619.05028
DOI: 10.1007/BF01788550
author: Pavol Hell
author: Katherine Heinrich
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: A vertex-numbering of an undirected graph G with N vertices is a bijection f of the vertex set of G onto the number set \(\{\) 1,2,...,N\(\}\). If \(\{\) v,w\(\}\) is an edge of G, then the number \(| f(v)-f(w)|\) is called an edge-differences of f. The bandsize of G, denoted by bs(G), is the minimum number of distinct edge-differences, taken over all vertex-numberings of G. The bandsize is compared with the radius of the graph. For the complete binary tree \(T_ n\) of height n the inequality \(n/7<bs(T_ n)<4n/5+2\) is presented.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4004213
zbMATH Keywords: vertex-numbering
zbMATH Keywords: edge-differences
zbMATH Keywords: bandsize
zbMATH Keywords: radius
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q4111617
cites work: Complexity Results for Bandwidth Minimization
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: On cross-bandwidth
cites work: Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
cites work: Row-column permutation of sparse matrices
full work available at URL: https://doi.org/10.1007/bf01788550
OpenAlex ID: W2020046666
description: scientific article; zbMATH DE number 4004213