Partial cubes with pre-hull number at most 1

2019/01/19 by Polat, Norbert
#05C75 (Primary) #52A37 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1901.06571

Abstract

We prove that a connected bipartite graph G is a partial cube if and only if the set of attaching points of any copoint of G is convex. A consequence of this result is that any connected bipartite graph with pre-hull number at most 1 is a partial cube. We show that the class of partial cubes with pre-hull number at most 1 is closed under gated subgraphs, gated amalgams and cartesian products.

Related

• Convexity in partial cubes: the hull number
• Partial cubes: structures, characterizations, and constructions
• Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
• Peano partial cubes
• Two-dimensional partial cubes