Information Technology Reference
In-Depth Information
to both endpoints of the original wheel edge. Figure
5
shows an example. Let
us call
C
g
the cycle induced by the non-center vertices. Let us first look at the
edge connectivity of
G
. Vertices belonging to one of the
K
t−
1
have degree
t
.On
the other hand we easily construct
t
edge-disjoint paths between every pair of
vertices. Hence, the edge connectivity of
G
equals
t
.
We now show that the set of edges
of
C
g
is a guarding set.
Suppose the opposite: there exists
an acyclic orientation for which no
edge of the cycle is flippable, hence all
of them are transitive. Since
C
g
is odd,
there must exist two consecutive edges
of
C
g
with the same orientation, say
uv
and
vw
, with
uv
oriented from
u
to
v
,and
vw
from
v
to
w
.
The only way to make
vw
transi-
tive is to construct an oriented path
from
v
to
w
going through the center
c
. Hence there must exist an oriented
path of the form
vPc
, where
P
is a
path in the complete graph
K
t−
1
attached to
v
. To make
uv
transitive we need a
directed path
cP
v
. The oriented cycle
vPcP
v
is in contradiction to the acyclic-
ity. Therefore, some edge of
C
g
is always flippable.
Fig. 5.
Agraph
G
with edge connectivity
6 and a guarding set of size 3.
5 Median Graphs
A median graph is an undirected
graph in which every three vertices
x
,
y
,and
z
have a unique
median
,
i.e., a vertex
μ
(
x, y, z
) that belongs
to shortest paths between each pair
of
x
,
y
,and
z
. Imrich, Klavzar, and
Mulder [
15
] proposed the following
construction of median graphs: Start
with any triangle-free graph
G
=
(
V,E
). First add an apex vertex
x
adjacent to all vertices of
V
, then sub-
divide every edge of
E
once, and let
G
be the resulting graph. Figure
6
illus-
trates the construction.
We only need that
G
is a partial
cube. This can be shown with the explicit construction of an isometric embedding
into
Q
n
.Let
V
=
G
G´
x
Fig. 6.
Agraph
G
and the
G
obtained by
the construction.
{
v
1
,...,v
n
}
and map these vertices bijectively to the standard
basis, i.e.,
v
i
e
i
.Apex
x
is mapped to 0 and the subdivision vertex
w
ij
of an edge
v
i
v
j
is mapped to
e
i
+
e
j
. The embedding shows that the zones
ₒ
Search WWH ::
Custom Search