Information Technology Reference
In-Depth Information
E
E
D
D
B
B
A
F
A
F
C
C
G
G
H
H
Fig. 1.
Digraph (the left picture) and its line digraph (the right picture)
1:1
1:0
0:0
0:1
1:2
Fig. 2.
The graph
PD
(
q, m
)with
q
=3,
m
=2
Lemma 1.
Let D be a k-regular digraph with n vertices. Then, we have
(
k
!)
n
(
k−
1)
k
E
(
L
(
D
)) =
E
(
D
)
.
3
Projective de Bruijn Graph
Let
q
be a prime power,
F
q
the
q
-element field, and
m
a positive integer.
Definition 2.
We define the q-ary projective de Bruijn graph of degree m,de-
noted by PD
(
q, m
)
,asfollows.LetP
(
q, m
1)
O
denotes the set of points in
the m-dimensional projective space supplemented with a formal element O
m
:=
[0 : 0 :
−
···
:0]
(an m-tuple of 0s). (1) V
(
PD
(
q, m
)) :=
P
(
q, m
−
1)
O
,(2)
A
(
PD
(
q, m
)) :=
P
(
q, m
)
O
,and(3)anarc
[
x
0
:
···
:
x
m
]
∈
A
(
PD
(
q, m
))
has
its origin at
[
x
0
:
···
:
x
m−
1
]
∈
V
(
PD
(
q, m
))
and its target at
[
x
1
:
···
:
x
m
]
∈
V
(
PD
(
q, m
))
.
There are three special vertices in PD
(
q, m
)
: A
m
=[1:0:
···
:0]
m
, B
m
=
[0 :
···
:0:1]
m
,andO
m
:= [0 :
···
:0]
(and special arrows A
m
+1
, B
m
+1
,and
O
m
+1
).
Remark 1.
It is easy to check that the digraph
PD
(
q, m
)hasaloopat
O
m
,and
(
q
−
1) multiple arrows from
A
m
to
B
m
. In addition, the out-degree and in-degree
