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

DOI10.1016/J.DISC.2019.111678zbMATH Open1433.05228arXiv1606.02154OpenAlexW2980051422MaRDI QIDQ2297708FDOQ2297708

Authors: Victor Chepoi, Kolja Knauer, Tilen Marc 

Publication date: 20 February 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (14)

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

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)