The treewidth and pathwidth of hypercubes |
| |
Authors: | L. Sunil Chandran |
| |
Affiliation: | Max-Planck-Institute für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany |
| |
Abstract: | The d-dimensional hypercube, Hd, is the graph on 2d vertices, which correspond to the 2dd-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the qdd-vectors where the components are from the set {0,1,2,…,q-1}, and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the . |
| |
Keywords: | Treewidth Pathwidth Hypercube Hamming graph |
本文献已被 ScienceDirect 等数据库收录! |
|