Partial cubes: Structures, characterizations, and constructions
From MaRDI portal
Publication:998441
DOI10.1016/J.DISC.2007.10.025zbMATH Open1186.05102arXiv0704.0010OpenAlexW2045413572MaRDI QIDQ998441FDOQ998441
Authors: J. Martínez 
Publication date: 28 January 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: Partial cubes are isometric subgraphs of hypercubes. Structures on a graph defined by means of semicubes, and Djokovi'{c}'s and Winkler's relations play an important role in the theory of partial cubes. These structures are employed in the paper to characterize bipartite graphs and partial cubes of arbitrary dimension. New characterizations are established and new proofs of some known results are given. The operations of Cartesian product and pasting, and expansion and contraction processes are utilized in the paper to construct new partial cubes from old ones. In particular, the isometric and lattice dimensions of finite partial cubes obtained by means of these operations are calculated.
Full work available at URL: https://arxiv.org/abs/0704.0010
Recommendations
Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Geometry of cuts and metrics
- Antipodal graphs and oriented matroids
- Isometric embedding in products of complete graphs
- Distance-preserving subgraphs of hypercubes
- Title not available (Why is that?)
- Isometric embeddings in Hamming graphs
- Title not available (Why is that?)
- Collapse of the metric hierarchy for bipartite graphs
- Well-graded families of relations
- Retracts of strong products of graphs
- Title not available (Why is that?)
- Hypermetric Spaces and the Hamming Cone
- Title not available (Why is that?)
- The lattice dimension of a graph
- Title not available (Why is that?)
- Isometric subgraphs of Hamming graphs and d-convexity
- Separation of two convex sets in convexity structures
- Media theory: Representations and examples
Cited In (45)
- On even and harmonic-even partial cubes.
- Hunting for cubic partial cubes
- Fast recognition algorithms for classes of partial cubes
- Recognizing partial cubes in quadratic time
- Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
- There are no finite partial cubes of girth more than 6 and minimum degree at least 3
- \(\Theta\)-graceful labelings of partial cubes
- On the dimension of vertex labeling of k-uniform dcsl of an even cycle
- Cubic partial cubes from simplicial arrangements
- Cubical local partial orders on cubically subdivided spaces -- existence and construction
- Friendship-Like Graphs and It’s Classiffication
- Partial cubes are distance graphs
- A characterization of planar partial cubes
- Title not available (Why is that?)
- Partial cubes and their \(\tau\)-graphs
- Cubic inflation, mirror graphs, regular maps, and partial cubes
- Tribes of cubic partial cubes
- On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
- The hypergraph of \(\Theta \)-classes and \(\Theta \)-graphs of partial cubes.
- On some characterizations of antipodal partial cubes
- Title not available (Why is that?)
- Constructions of 1-uniform dcsl graphs using well-graded families of sets
- On antipodal and diametrical partial cubes
- Hypercube embeddings and Cayley graphs generated by transpositions
- Characterization of 2-arc-transitive partial cubes
- Crossing Graphs as Joins of Graphs and Cartesian Products of Median Graphs
- A characterization of regular partial cubes whose all convex cycles have the same lengths
- Some properties of Bowlin and Brin's color graphs
- Braid graphs in simply-laced triangle-free Coxeter systems are partial cubes
- Tiled partial cubes
- Netlike partial cubes. I. General properties
- A correction of a characterization of planar partial cubes
- Computing distance moments on graphs with transitive Djoković-Winkler relation
- Graphs and cubes
- Tree-like isometric subgraphs of hypercubes
- Axiomatic characterization of the interval function of partial cubes and partial Hamming graphs
- Convex excess in partial cubes
- On finding convex cuts in general, bipartite and plane graphs
- Two-dimensional partial cubes
- Learning graphs and 1-uniform dcsl graphs
- On semicube graphs
- A theorem on Wiener-type invariants for isometric subgraphs of hypercubes
- Partial cubes and Archimedean tilings
- On some properties of antipodal partial cubes
- On partial cubes, well-graded families and their duals with some applications in graphs
This page was built for publication: Partial cubes: Structures, characterizations, and constructions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q998441)
