Covering Partial Cubes with Zones - Discrete and Computational Geometry and Graphs - page 7

the path. Then by definition, no edge of S is in the path, hence all of them
are transitive, and S is not a guarding set. Conversely, suppose that S is not
guarding. Then there exists an acyclic orientation of G in which all edges of S
are transitive. The corresponding ordering of the vertices in V yields a Hamilton
path in H .

4.2 Special Cases and an Upper Bound

Lemma 1. The minimum size of a guarding set in a complete graph on n ver-
tices is n − 1 .

Proof. First note that there always exists a guarding set of size n − 1 that consists

of all edges incident to one vertex.
Now we need to show that any other edge subset of smaller size is not a

guarding set. This amounts to stating that every graph with at least 2 −

2)
edges has a Hamilton path. To see this, proceed by induction on n . Suppose this
holds for graphs with less than n vertices. Consider a set S of at most n

( n −

− 2

edges of the complete graph. Let u, v be two vertices with uv ∈ S . One of the

two vertices, say v , is incident to at most ( n − 2) / 2 edges of S . Consider a

Hamilton path on the n = v , which exists by induction hypothesis.

Then vertex v must have one or two incident edges that do not belong to S and
connect v to the first, or the last, or two consecutive vertices of this path. Hence
we can integrate v in the Hamilton path.

− 1 vertices

Since acyclic orientations of the complete graph K n correspond to the permu-
tations of S n , this is in fact the solution to the puzzle “hitting a consecutive
pair” in the introduction. The dual graph of the arrangements of hyperplanes
corresponding to the complete graph (graphic hyperplane arrangement of K n )
is the skeleton graph of the permutohedron. Hence the above result can also be
stated in the following form.

Corollary 1. The minimum size of a set of zones covering the vertices of the
skeleton graph of the n -dimensional permutohedron is n − 1 .

We now give a simple, polynomial-time computable upper bound on the size of
a guarding set. A set C ↆ E is an edge cut whenever the graph ( V,E \ C )isnot

connected.

Theorem 4. Every edge cut of G is a guarding set of G .

Proof. Consider an edge cut C E and an acyclic orientation A G of G . This

acyclic orientation can be used to define a partial order on V . Let us consider a
total ordering of V that extends this partial order, and pick an edge e = uv

ↆ

C
that minimizes the rank difference between u and v . We claim that e is flippable.
Suppose for the sake of contradiction that e is not flippable. Then e must be
transitive and there exists a directed path P in A G between u and v that does
not use e . Since C is a cut, u and v belong to distinct connected components of

∈