scientific article; zbMATH DE number 125454

From MaRDI portal
Publication:4027153





[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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027153)