Information Technology Reference
In-Depth Information
1:1
AOB
2
1:2
Fig. 4.
Digraph
PD
(
q, m
)for
q
=3,
m
=2
AOB
m
). The obtained digraph is denoted by PD
(
q, m
)
. Thus, the incoming
arrows to AOB
m
in PD
(
q, m
)
is the incoming arrows to A
m
in PD
(
q, m
)
,and
outgoing arrows from AOB
m
are those from B
m
in PD
(
q, m
)
. This digraph has
no multiple arrows.
Lemma 3.
Suppose m
≥
2
. There is a natural q
!
to 1 mapping
(
PD
(
q, m
))
(
PD
(
q, m
))
.
E
→E
As a corollary, we have
E
(
PD
(
q, m
)) =
q
!
E
(
PD
(
q, m
))
.
Proof.
Let
C
be an Eulerian circuit of
PD
(
q, m
). Let
C
be a cyclic sequence
of arrows of
PD
(
q, m
) obtained by simply removing the
q
arrows from
A
m
to
B
m
from
C
.Since
A
m
and
B
m
are contracted in
PD
(
q, m
),
C
is a circuit,
and easily seen to be an Eulerian circuit. Conversely, if we fix
C
,then
C
is
obtained by adding an arrow from
A
m
to
B
m
at each place in
C
where
C
goes
over
AOB
m
. Thus, this mapping is
q
!to1.
Note that the above does not hold for
m
=1,since
E
(
PD
(
q,
1)) = (
q
−
1)!.
Lemma 4
L
(
PD
(
q, m
)) =
PD
(
q, m
+1)
.
Proof.
Note that these graphs have no multiple arrows. As for the vertex sets,
V
(
L
(
PD
(
q, m
))) :=
A
(
PD
(
q, m
))
is obtained from
A
(
PD
(
q, m
)) =
P
(
q, m
)byremoving
A
m
+1
,O
m
+1
,B
m
+1
and
adding an element named
AB
m
+1
. By identifying
AB
m
+1
with
AOB
m
+1
∈
