Hypercellular graphs: partial cubes without Q₃^- as partial cube minor

DOI10.1016/J.DISC.2019.111678MaRDI QIDQ2297708zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Kolja Knauer, Tilen Marc

Publication date 20 February 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02154

zbMATH Keywords

partial cubemedian graphscellular graphshypercellular graphspartial cube minors

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We investigate the structure of isometric subgraphs of hypercubes (i.e., partial cubes) which do not contain finite convex subgraphs contractible to the 3-cube minus one vertex $Q_3^{-}$ (here contraction means contracting the edges corresponding to the same coordinate of the hypercube). Extending similar results for median and cellular graphs, we show that the convex hull of an isometric cycle of such a graph is gated and isomorphic to the Cartesian product of edges and even cycles. Furthermore, we show that our graphs are exactly the class of partial cubes in which any finite convex subgraph can be obtained from the Cartesian products of edges and even cycles via successive gated amalgams. This decomposition result enables us to establish a variety of results. In particular, it yields that our class of graphs generalizes median and cellular graphs, which motivates naming our graphs hypercellular. Furthermore, we show that hypercellular graphs are tope graphs of zonotopal complexes of oriented matroids. Finally, we characterize hypercellular graphs as being median-cell -- a property naturally generalizing the notion of median graphs.

Recommendations

• Netlike partial cubes. I. General properties
• Partial cubes: Structures, characterizations, and constructions
• Partial cubes and their \(\tau\)-graphs
• Tree-like isometric subgraphs of hypercubes
• Fast recognition algorithms for classes of partial cubes

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 26592 (Why is no real title available?)
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 1221771 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• A Tverberg-type generalization of the Helly number of a convexity space
• Bucolic complexes
• COMs: complexes of oriented matroids
• Cellular bipartite graphs
• Combinatorics of lopsided sets
• Convex excess in partial cubes
• Convexity in partial cubes: the hull number
• Cross-cloning and antipodal graphs
• Distance-preserving subgraphs of hypercubes
• Gated sets in metric spaces
• Graphs of some CAT(0) complexes
• Graphs with intrinsic s3 convexities
• Hyperplane arrangements with a lattice of regions
• Isometric subgraphs of Hamming graphs and d-convexity
• Lopsided sets and orthant-intersection by convex sets
• Matching binary convexities
• Median Algebra
• Median algebras
• Metric graph theory and geometry: a survey
• Netlike partial cubes II. Retracts and netlike subgraphs
• Netlike partial cubes III. The median cycle property
• Netlike partial cubes, IV: Fixed finite subgraph theorems
• Netlike partial cubes. I. General properties
• On compact median graphs
• Retracts of hypercubes
• Separation of two convex sets in convexity structures
• Superextensions and the depth of median graphs
• The algebra of metric betweenness. I: Subdirect representation and retraction
• Tverberg numbers for cellular bipartite graphs
• Two-ended regular median graphs

Cited in

(14)

• Ample completions of oriented matroids and complexes of uniform oriented matroids
• Labeled sample compression schemes for complexes of oriented matroids
• Two-dimensional partial cubes
• Unlabeled sample compression schemes for oriented matroids
• The hypergraph of \(\Theta \)-classes and \(\Theta \)-graphs of partial cubes.
• On some characterizations of antipodal partial cubes
• Helly groups
• Finitary affine oriented matroids
• First-order logic axiomatization of metric graph theory
• On some properties of antipodal partial cubes
• On tope graphs of complexes of oriented matroids
• Corners and simpliciality in oriented matroids and partial cubes
• Graphs with \(G^p\)-connected medians
• The edge general position problem

This page was built for publication: Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor

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