z-logo
open-access-imgOpen Access
Covering Partial Cubes with Zones
Author(s) -
Jean Cardinal,
Stefan Felsner
Publication year - 2015
Publication title -
the electronic journal of combinatorics/the journal of combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.703
H-Index - 52
eISSN - 1097-1440
pISSN - 1077-8926
DOI - 10.37236/5076
Subject(s) - combinatorics , mathematics , partially ordered set , hypercube , bipartite graph , embedding , discrete mathematics , linear extension , graph , computer science , artificial intelligence
A partial cube is a graph having an isometric embedding in a hypercube. Partial cubes are characterized by a natural equivalence relation on the edges, whose classes are called zones. The number of zones determines the minimal dimension of a hypercube in which the graph can be embedded. We consider the problem of covering the vertices of a partial cube with the minimum number of zones. The problem admits several special cases, among which are the following:cover the cells of a line arrangement with a minimum number of lines,select a smallest subset of edges in a graph such that for every acyclic orientation, there exists a selected edge that can be flipped without creating a cycle,find a smallest set of incomparable pairs of elements in a poset such that in every linear extension, at least one such pair is consecutive,find a minimum-size fibre in a bipartite poset.We give upper and lower bounds on the worst-case minimum size of a covering by zones in several of those cases. We also consider the computational complexity of those problems, and establish some hardness results.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here