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)

• There are no finite partial cubes of girth more than 6 and minimum degree at least 3
• On even and harmonic-even partial cubes.
• Friendship-Like Graphs and It’s Classiffication
• A correction of a characterization of planar partial cubes
• On antipodal and diametrical partial cubes
• Computing distance moments on graphs with transitive Djoković-Winkler relation
• A characterization of planar partial cubes
• Crossing Graphs as Joins of Graphs and Cartesian Products of Median Graphs
• Some properties of Bowlin and Brin's color graphs
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• On semicube graphs
• Tree-like isometric subgraphs of hypercubes
• On the dimension of vertex labeling of k-uniform dcsl of an even cycle
• On finding convex cuts in general, bipartite and plane graphs
• Two-dimensional partial cubes
• Braid graphs in simply-laced triangle-free Coxeter systems are partial cubes
• Hunting for cubic partial cubes
• Axiomatic characterization of the interval function of partial cubes and partial Hamming graphs
• Partial cubes are distance graphs
• Cubic partial cubes from simplicial arrangements
• scientific article; zbMATH DE number 2185257 (Why is no real title available?)
• Partial cubes and Archimedean tilings
• Characterization of 2-arc-transitive partial cubes
• Convex excess in partial cubes
• The hypergraph of \(\Theta \)-classes and \(\Theta \)-graphs of partial cubes.
• A characterization of regular partial cubes whose all convex cycles have the same lengths
• Partial cubes and their \(\tau\)-graphs
• On some characterizations of antipodal partial cubes
• Hypercube embeddings and Cayley graphs generated by transpositions
• Cubical local partial orders on cubically subdivided spaces -- existence and construction
• Tiled partial cubes
• Netlike partial cubes. I. General properties
• On some properties of antipodal partial cubes
• A theorem on Wiener-type invariants for isometric subgraphs of hypercubes
• Fast recognition algorithms for classes of partial cubes
• Learning graphs and 1-uniform dcsl graphs
• Constructions of 1-uniform dcsl graphs using well-graded families of sets
• On partial cubes, well-graded families and their duals with some applications in graphs
• Cubic inflation, mirror graphs, regular maps, and partial cubes
• Recognizing partial cubes in quadratic time
• Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
• Graphs and cubes
• \(\Theta\)-graceful labelings of partial cubes
• Tribes of cubic partial cubes
• scientific article; zbMATH DE number 6008745 (Why is no real title available?)

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)