Information Technology Reference
In-Depth Information
·
·
Keywords
Girth
Moore bound
Graphs
·
Mathematics Subject Classification (2010)
Primary 05C35
Secondary 05C81
10.1 Introduction
The Moore bound (see Theorem 3.1) gives a lower bound on the order of any simple
undirected graph, based on its minimum degree and girth. Alon et al. [
AHL02
]
showed that the same bound holds with the minimum degree replaced by the average
degree. Later, Hoory [
Hoo02
] obtained a better bound for simple bipartite graphs.
We reprove the results of Alon et al. [
AHL02
] and Hoory [
Hoo02
] using information
theoretic arguments based on nonreturning random walks on the graph.
The chapter has three sections: In Sect.
10.2
we introduce the relevant notation and
terminology. In Sect.
10.3
, we present the information theoretic proof of the result of
Alon et al. [
AHL02
]; in Sect.
10.4
, we present a similar proof of the result of Hoory
[
Hoo02
] for bipartite graphs.
10.2 Preliminaries
,let
G
,
E
For an undirected simple graph
G
=
(
V
,
E
)
=
(
V
),
be the directed version
of
G
, where for each undirected edge of the form
{
v,v
}
in
E
, we place two directed
edges in
E
, one of the form
(v,v)
and another of the form
(v, v)
. Similarly, for an
,let
G
V
R
,
E
LR
E
RL
)
=
(
V
L
,
V
R
,
)
=
(
V
L
,
undirected bipartite graph
G
E
be the
{
v,v
}
directed version of
G
, where for each undirected edge of the form
in
E
, with
in
E
LR
, and another
v
V
L
and
v
V
R
, we place one directed edge of the form
(v,v)
in
E
RL
.
We will consider
nonreturning
walks on
G
, that is, walks where the edges corre-
sponding to the same undirected edge of
G
do not appear in succession. For a vertex
v
of the form
(v, v)
denote the number of nonreturning walks in
G
starting at
,let
n
i
(v)
v
and consisting
denote the number of nonreturning walks in
G
of
i
edges. For an edge
∃
e
,let
n
i
(
∃
e
)
starting with
e
).
Our proofs will make use of information theoretic ideas. Similar ideas have
been employed in various combinatorial proofs to succinctly present arguments that
involve averaging and convexity. More examples can be found in the references
[
CT91
,
Kah02
,
LL13
,
Rad99
,
Rad01
].
Let
X
be a random variable taking values in a finite set. Let support
∃
e
and consisting of exactly
i
+
1 edges (including
∃
(
X
)
be the set
of values that
X
takes with positive probability. The entropy of
X
is
[
]=−
[
=
]
[
=
]
.
H
X
Pr
X
x
log
2
Pr
X
x
x
support
(
X
)
