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

      0 references
      21 February 1993
      0 references
      cubical graphs
      0 references
      hypercube
      0 references
      maximal cubical dimension
      0 references
      upper bounds
      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

      Identifiers