Convexity in partial cubes: the hull number

DOI10.1016/j.disc.2015.10.032zbMath1327.05086MaRDI 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

90C27: Combinatorial optimization

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

Related Items

Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids, Arrangements of pseudocircles: on circularizability, Hull and geodetic numbers for some classes of oriented graphs, Hull and geodetic numbers for some classes of oriented 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, There are no finite partial cubes of girth more than 6 and minimum degree at least 3, Two-dimensional partial cubes, On the \(P_3\)-hull number of some products of graphs, The hull number in the convexity of induced paths of order \(3\), Computing the hull number in toll convexity, \(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, On the parameterized complexity of the geodesic hull number, On tope graphs of complexes of oriented matroids, Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor, Daisy cubes and distance cube polynomial, Betweenness in graphs: a short survey on shortest and induced path betweenness, A correction of a characterization of planar 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