Partial cubes: Structures, characterizations, and constructions

DOI10.1016/J.DISC.2007.10.025MaRDI QIDQ998441zbMATH OpenOpenAlexFDO

Authors J. Martínez

Publication date 28 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypercubepartial cubesemicube

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

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.

Recommendations

• Partial cubes are distance graphs
• Partial cubes and their \(\tau\)-graphs
• Partial cubes and crossing graphs
• Tribes of cubic partial cubes
• Hunting for cubic partial cubes

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• scientific article; zbMATH DE number 3585454 (Why is no real title available?)
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• scientific article; zbMATH DE number 3234211 (Why is no real title available?)
• scientific article; zbMATH DE number 3080144 (Why is no real title available?)
• Antipodal graphs and oriented matroids
• Collapse of the metric hierarchy for bipartite graphs
• Distance-preserving subgraphs of hypercubes
• Geometry of cuts and metrics
• Hypermetric Spaces and the Hamming Cone
• Isometric embedding in products of complete graphs
• Isometric embeddings in Hamming graphs
• Isometric subgraphs of Hamming graphs and d-convexity
• Media theory: Representations and examples
• Retracts of strong products of graphs
• Separation of two convex sets in convexity structures
• The lattice dimension of a graph
• Well-graded families of relations

Cited in

(45)

• On some properties of antipodal partial cubes
• On partial cubes, well-graded families and their duals with some applications in graphs
• On even and harmonic-even partial cubes.
• Fast recognition algorithms for classes of partial cubes
• Hunting for cubic partial cubes
• Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
• Recognizing partial cubes in quadratic time
• 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
• Partial cubes and their \(\tau\)-graphs
• scientific article; zbMATH DE number 2185257 (Why is no real title available?)
• Cubic inflation, mirror graphs, regular maps, and partial cubes
• On some characterizations of antipodal partial cubes
• Tribes of cubic partial cubes
• The hypergraph of \(\Theta \)-classes and \(\Theta \)-graphs of partial cubes.
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• scientific article; zbMATH DE number 6008745 (Why is no real title available?)
• 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
• Some properties of Bowlin and Brin's color graphs
• A characterization of regular partial cubes whose all convex cycles have the same lengths
• Netlike partial cubes. I. General properties
• Braid graphs in simply-laced triangle-free Coxeter systems are partial cubes
• Tiled partial cubes
• 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
• Two-dimensional partial cubes
• On finding convex cuts in general, bipartite and plane graphs
• 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

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)