Back to Search
Start Over
The treewidth and pathwidth of hypercubes
- Source :
-
Discrete Mathematics . Feb2006, Vol. 306 Issue 3, p359-365. 7p. - Publication Year :
- 2006
-
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]
- Subjects :
- *GRAPH algorithms
*GRAPH theory
*HYPERCUBES
*TREE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 306
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 19847540
- Full Text :
- https://doi.org/10.1016/j.disc.2005.12.011