The bandwidth of the complement of a \(k\)-tree
type: Item
instance of: scholarly article
title: The bandwidth of the complement of a \(k\)-tree
zbMATH Open document ID: 0921.05055
author: Jinjiang Yuan
author: Yanpei Liu
published in: Applied Mathematics. Series B (English Edition)
publication date: 1999-09-12T00:00:00Z
review text: For an integer \(k\) define recursively a \(k\)-tree \(T\) on \(n\geq k\) vertices. If \(n=k\) then set \(T=K_k\). Now for \(n\geq k\) construct a \(k\)-tree \(T\) on \(n+1\) vertices by taking a \(k\)-tree \(T'\) on \(n\) vertices, and joining a new vertex with a clique of size \(k\) in \(T'\). The paper deals with the bandwidth problem for the complement of a \(k\)-tree. It is known that the bandwidth problem is NP-complete even for trees (\(k=1\)), and, thus, for \(k\)-trees. However, the bandwidth of the complement \(\overline T\) of a \(k\)-tree \(T\) can be precisely computed: \[ B(\overline T)=\begin{cases} n-k-1, &\text{if } T\cong K_k+\overline K_{n-k}\\ n-k-2, &\text{otherwise.}\end{cases} \] The lower bound is based on an isoperimetric approach. The upper bound is done essentially by induction by tedious consideration of several cases.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1286289
zbMATH Keywords: bandwidth
zbMATH Keywords: trees
reviewed by: Sergej L. Bezrukov
MaRDI profile type: Publication
full work available at URL: s11766-998-0058-7
OpenAlex ID: W2322449578
cites work: Q3328583
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q5289641
DOI: 10.1007/S11766-998-0058-7
description: scientific article; zbMATH DE number 1286289