1. The treewidth and pathwidth of hypercubes
- Author
-
Sunil Chandran, L. and Kavitha, T.
- Subjects
- *
GRAPH algorithms , *GRAPH theory , *HYPERCUBES , *TREE graphs - Abstract
Abstract: The d-dimensional hypercube, , is the graph on vertices, which correspond to the d-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 d-vectors where the components are from the set , 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 . [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF