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

C ), and P must use another edge e ∈ ( V,E C . By definition, the endpoints of

e have a rank difference that is smaller than that of u and v , contradicting the
choice of e .

\

An even shorter proof of the above can be obtained by reusing the following
observation from Cordovil and Forge [ 6 ]: for every acyclic orientation of G ,the
set of flippable edges is a spanning set of edges. Therefore, every such set must
intersect every edge cut.
While guarding sets are hard to recognize, even for complete graphs, we show
that a minimum-size guarding set can be found in polynomial time whenever the
input graph is chordal, i.e., if every cycle of length at least 4 has a chord. In that
case, the upper bound given by the minimum edge cut is tight, and the result
generalizes Lemma 1 .

Theorem 5. The minimum size of a guarding set in a chordal graph is the size
of a minimum edge cut.

Proof. We need to show that whenever a set S of edges of a chordal graph G
has size strictly less than the edge connectivity of G , there exists an acyclic
orientation of G in which all edges of S are transitive. Let us denote by k the
edge connectivity of G ,and n its number of vertices.
We proceed by induction on n . For the base case we consider complete graphs.
From Lemma 1 , the minimum size of a guarding set in K k +1 is k . Now suppose
the statement holds for every chordal graph with n 1 vertices, and that there

exists a k edge connected chordal graph G on n vertices with a guarding set
S of size k

−

1. Since G is chordal, it has at least two nonadjacent simplicial
vertices u and v , i.e., vertices whose neighborhood induces a clique. The degree
of both u and v is at least k . Hence one of them, say v , is incident to at most

−

edges of S .Nowremove v and consider, using
the induction hypothesis, a suitable acyclic orientation of the remaining graph.
This orientation induces a total order, i.e., a path p with d ( v ) vertices, on the
neighbors N ( v )of v . Then vertex v must have one or two incident edges that do
notbelongto S and connect v to the first, or the last, or two consecutive vertices
of path p . Hence we can integrate v in the path such that all the edges of S that
are incident to v are transitive. This yields a suitable acyclic orientation for G
and completes the induction step.

( k − 1) / 2 ≤ ( d ( v ) − 1) / 2

When the graph is not chordal, it may happen that the minimum size of a
guarding set is arbitrarily small compared to the edge connectivity. We can in
fact construct a large family of such examples.

Theorem 6. For every natural number t ≥ 2 and odd natural number g such

that 3 ≤ g ≤ t , there exists a graph G with edge connectivity t andaguarding

set of size g .

Proof. The graph G is constructed by considering a wheel with g + 1 vertices
and center c , and replacing every edge incident to the center c by a copy of the
complete graph K t− 1 such that each vertex of the complete graph is connected