Hypercellular graphs: Partial cubes without Q3− as partial cube minor

摘要

We investigate the structure of isometric subgraphs of hypercubes (i.e.,partial cubes) which do not contain finite convex subgraphs contractible to the3-cube minus one vertex $Q^-_3$ (here contraction means contracting the edgescorresponding to the same coordinate of the hypercube). Extending similarresults for median and cellular graphs, we show that the convex hull of anisometric cycle of such a graph is gated and isomorphic to the Cartesianproduct of edges and even cycles. Furthermore, we show that our graphs areexactly the class of partial cubes in which any finite convex subgraph can beobtained from the Cartesian products of edges and even cycles via successivegated amalgams. This decomposition result enables us to establish a variety ofresults. In particular, it yields that our class of graphs generalizes medianand cellular graphs, which motivates naming our graphs hypercellular.Furthermore, we show that hypercellular graphs are tope graphs of zonotopalcomplexes of oriented matroids. Finally, we characterize hypercellular graphsas being median-cell -- a property naturally generalizing the notion of mediangraphs.