No label defined (Q4027153)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 125454
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 125454 |
Statements
21 February 1993
0 references
cubical graphs
0 references
hypercube
0 references
maximal cubical dimension
0 references
upper bounds
0 references
0.8063464760780334
0 references
0.8049172759056091
0 references
0.7934315204620361
0 references
0.7928823232650757
0 references
[For the entire collection see Zbl 0748.00023.] The hypercube of dimension \(n\), denoted by \(Q_ n\), is the graph of \(2^ n\) vertices labelled by binary vectors of length \(n\), an edge joining two vertices whenever the corresponding vectors differ in exactly one coordinate. A graph is called cubical if it is a subgraph of \(Q_ n\) for some \(n\). The maximal cubical dimension of \(G\), denoted \(\max\dim(G)\), is the largest \(n\) such that \(G\) is a subgraph of \(Q_ n\) and for each \(i\in\{1,\dots,n\}\) there are two adjacent vertices in \(G\) which differ in the \(i\)-th coordinate. This paper investigates the maximal cubical dimension of \(k\)-edge-connected graphs and use this to obtain upper bounds for the cubical dimension of graphs with minimal degree at least 2.
0 references