Information Technology Reference
In-Depth Information
Definition.
For a vertex
v
of a graph
G
,a
v
-tree
is a spanning tree of
G
which
contains all the edges incident to
v
. We denote by
S
G
(
v
)thesetofall
v
-trees
in
G
.
Lemma 3.
Let
(
V, ∗
)
be a non-confusing travel groupoid on a finite connected
graph
G
. For an element
v
of
V
,let
T
v
be the graph defined by
V
(
T
v
):=
V
and
E
(
T
v
):=
{{u, u ∗ v}|u ∈ V \{v}}.
T
v
is a
v
G
Then,
-tree of
.
Proof.
Since (
V, ∗
)ison
G
, for any two distinct elements
u
and
v
in
V
,
{u, u∗v}
is
an edge of
G
. Therefore, we have
E
(
T
v
)
ↆ E
(
G
). Moreover,
V
(
T
v
)=
V
=
V
(
G
).
T
v
is a spanning subgraph of
G
T
v
,wehave
So
. By the definition of the graph
|E
T
v
)
|≤|V |−
V, ∗
(
1. Since (
) is non-confusing, it follows from Theorem
1
that
any vertex
u
of
T
v
distinct from
v
is connected to the vertex
v
by a path
P
uv
in
k
G
, where
P
uv
is of the form (
u ∗
0
v,...,u∗
v
) for some positive integer
k
. Since
i
+1
i
i
i
+1
u ∗
v
=(
u ∗
v
)
∗ v
, the edge
{u ∗
v, u∗
v}
of the path
P
uv
is also an edge of
T
v
for any
i ∈{
0
,
1
,...,k−
1
}
. Therefore, the path
P
uv
from
u
to
v
in
G
is also
a path in
T
v
. So we can conclude that
T
v
is connected. Since
T
v
is a connected
graph with
|E
(
T
v
)
|≤|V
(
T
v
)
|−
1,
T
v
is a tree. Thus,
T
v
is a spanning tree of
G
. For each vertex
x
which is adjacent to the vertex
v
in
G
,wehave
x ∗ v
=
v
and therefore
{x, v}∈E
(
T
v
). So, all the edges incident to the vertex
v
in
G
are
contained in
T
v
. Hence, the graph
T
v
is a
v
-tree of
G
.
The following theorem is our main result.
Theorem 4.
Let
be a finite connected graph. Then, there exists a one-to-one
correspondence between the set
ʠ
v∈V
(
G
)
S
G
(
G
v
)
and the set of all non-confusing
travel groupoids on
G
.
Proof.
Let
V
:=
V
(
G
), and let
N
G
be the set of all non-confusing travel groupoids
on
G
. Note that, since
G
is finite, both the sets ʠ
v∈V
S
G
(
v
)and
N
G
are finite.
For any (
T
v
)
v∈V
∈
ʠ
v∈V
(
G
)
S
G
(
v
), we define a groupoid on
V
as follows: For
two distinct elements
u
and
v
in
V
,
u ∗ v
is defined to be the vertex adjacent
to
u
which is on the unique path from
u
to
v
in the tree
T
v
.If
u
=
v
, then let
u ∗ v
=
u
. We show that this groupoid (
V, ∗
) is a non-confusing travel groupoid.
First, we check that (
V, ∗
) satisfies the axioms (t1) and (t2). Take any two
distinct elements
u
and
v
in
V
.Let
w
:=
u ∗ v
. Then
{u, w}∈E
(
G
). Therefore
{w, u}∈E
(
T
u
) and we have (
u ∗ v
)
∗ u
=
w ∗ u
=
u
. Moreover, if
u
=
v
, then
(
u ∗ v
)
∗ u
=(
u ∗ u
)
∗ u
=
u ∗ u
=
u
. Thus the axiom (t1) holds. Again, take any
two distinct elements
u
and
v
in
V
.If
u
and
v
are adjacent (i.e.
{u, v}∈E
(
G
)),
then
{u, v}∈E
(
T
v
) and therefore (
u ∗ v
)
∗ v
=
v ∗ v
=
v
=
u
.If
u
and
v
are
not adjacent, then
u ∗ v
=
v
and the element (
u ∗ v
)
∗ v
is the third vertex of the
path from
u
to
v
in the tree
T
v
and therefore (
u ∗ v
)
∗ v
is not the element
u
.
Thus the axiom (t2) holds. So, (
V, ∗
) is a travel groupoid. Second, we check that
(
V, ∗
) is non-confusing. Take any two distinct elements
u
and
v
in
V
.Let
k
be
u
v
T
v
. Then, it follows from the definition of
the length of the path from
to
in
Search WWH ::
Custom Search