Information Technology Reference
In-Depth Information
O
m
1
O
m
1
O
m
B
m
1
A
m
1
B
m
1
A
m
1
B
m
B
m
A
m
A
m
Fig. 5.
Three arrows
O
m
+1
,A
m
+1
,B
m
+1
in
PD
(
q, m
) (the left picture) and its line
digraph
L
(
PD
(
q, m
)) (the right picture)
V
(
PD
(
q, m
+1)), we have identification
V
(
L
(
PD
(
q, m
))) =
V
(
PD
(
q, m
+1)).
As for the arrow sets, there is a bijection
A
(
L
(
PD
(
q, m
))
A
(
PD
(
q, m
+1))
→
defined as follows. The left hand side is a pair of adjacent arrows of
PD
(
q, m
),
say
P
m
+1
,Q
m
+1
. There are four cases.
-
Case 1:
P
m
+1
=
AB
m
+1
and
Q
m
+1
=
AB
m
+1
. Then,
P
m
+1
,Q
m
+1
are in
, and are adjacent vertices in
PD
(
q, m
+1),
hence
P
m
+1
Q
m
+1
is an arrow in
PD
(
q, m
+1).
-
Case 2:
P
m
+1
=
AB
m
+1
and
Q
m
+1
P
(
q, m
)
\{
A
m
+1
,O
m
+1
,B
m
+1
}
=
AB
m
+1
.Inthiscase,
B
m
+1
is adjacent
to
Q
m
+1
in
A
(
PD
(
q, m
)). (See Definition 4). Then, an arrow in
PD
(
q, m
+1)
that connects the vertex
AOB
m
+1
to
Q
m
+1
is assigned.
-
Case 3:
P
m
+1
=
AB
m
+1
and
Q
m
+1
=
AB
m
+1
. This case is similar (symmet-
ric) to Case 2.
-
Case 4:
P
m
+1
=
AB
m
+1
and
Q
m
+1
=
AB
m
+1
. This does not happen since
AB
m
+1
is not a loop.
It is straightforward to check that this mapping is a bijection: Case 1 is easy, and
for the other cases by the case division, which is left to the reader. See Figures 5
and 6 for the structure for Cases 2 and 3.
Remark 2.
A more conceptual proof is as follows. Let
D
(
q, m
)bethe
q
-ary de
Bruijn graph of degree
m
[5]. By definition, we have
L
(
D
(
q, m
)) =
D
(
q, m
+1).
The action of
F
q
×
is free except for the neighborhood of
A
m
,O
m
,B
m
. Thus, by
taking the quotient, we know that
L
(
PD
(
q, m
)) is isomorphic to
PD
(
q, m
+1),
except for the neighborhoods of these three vertices. Then, looking the non-
regularity around the fixed points, we are lead to the above lemma.
