Convexity in partial cubes: the hull number

DOI10.1016/j.disc.2015.10.032zbMath1327.05086OpenAlexW2463927641MaRDI QIDQ898152

Kolja Knauer, Marie Albenque

Publication date: 8 December 2015

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

Full work available at URL: https://doi.org/10.1016/j.disc.2015.10.032

zbMATH Keywords

topological representationalgorithmic complexitypartial cubehull numberposet dimensionupper locally distributive lattice

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Related Items

There are no finite partial cubes of girth more than 6 and minimum degree at least 3 ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids ⋮ Computing the hull number in toll convexity ⋮ A correction of a characterization of planar partial cubes ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ Corners and simpliciality in oriented matroids and partial cubes ⋮ First-order logic axiomatization of metric graph theory ⋮ On the parameterized complexity of the geodesic hull number ⋮ Arrangements of pseudocircles: on circularizability ⋮ On tope graphs of complexes of oriented matroids ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ Hull and geodetic numbers for some classes of oriented graphs ⋮ Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor ⋮ Daisy cubes and distance cube polynomial ⋮ The hull number in the convexity of induced paths of order \(3\) ⋮ Betweenness in graphs: a short survey on shortest and induced path betweenness ⋮ Two-dimensional partial cubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the geodetic and the hull numbers in strong product graphs
• Antipodal graphs and oriented matroids
• A use for frequently rediscovering a concept
• Isometric embedding in products of complete graphs
• On the computation of the hull number of a graph
• The hull number of a graph
• Two poset polytopes
• Optimal packing and covering in the plane are NP-complete
• Sur les matroides orientes de rang 3 et les arrangements de pseudodroites dans le plan projectif réel
• On the Steiner, geodetic and hull numbers of graphs
• On the hull number of some graph classes
• Topes of oriented matroids and related structures
• Distance-preserving subgraphs of hypercubes
• Lattices with unique irreducible decompositions
• Geodetic Number versus Hull Number in $P_3$-Convexity
• Convex excess in partial cubes
• On the Hull Number of Triangle-Free Graphs
• ULD-Lattices and Δ-Bonds
• Isometric Diamond Subgraphs
• The Complexity of the Partial Order Dimension Problem
• Graphs with intrinsic s3 convexities
• Lectures on Polytopes
• Oriented Matroids
• On the Addressing Problem for Loop Switching
• Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs
• On the complexity of \(k\)-SAT