The Non-confusing Travel Groupoids on a Finite Connected Graph - Discrete and Computational Geometry and Graphs - page 15

A geodetic graph is a connected graph in which there exists a unique shortest
path between any two vertices. Let

G be a geodetic graph, and let V := V ( G ).

For two vertices u and v of G ,let A G ( u, v ) denote the vertex adjacent to u which

is on the unique shortest path from u to v in G . Define a binary operation ∗ on

V as follows: For all u, v ∈ V ,let u ∗ v := A G ( u, v )if u = v and u ∗ v := u if

u = v . This groupoid ( V, ∗ ) is called the proper groupoid of the geodetic graph

G . Remark that the proper groupoid of any geodetic graph is a travel groupoid.

Let ( V, ∗ ) be a travel groupoid, and let G be a graph. We say that ( V, ∗ ) is

on G or that G has ( V, ∗ )if V ( G )= V and E ( G )= {{u, v}|u, v ∈ V,u =

v, and u ∗ v = v} . Note that every travel groupoid is on exactly one graph.

0

Let ( V, ∗ ) be a travel groupoid. For u, v ∈ V , we define u ∗ v := u and

i +1 i j k

u∗ v := ( u∗ v ) ∗v for every nonnegative integer i . It is clear that ( u∗ v ) ∗ v =

j + k

u∗ v holds for any nonnegative integers j and k . Note that, for any two distinct

elements u and v in V , it holds that u∗v = u (see [ 5 , Proposition 2 (2)]) and that

2

u ∗ v = u by (t2). An ordered pair ( u, v ) of two distinct elements of V is called

i

a confusing pair in ( V, ∗ ) if there exists an integer i ≥ 3 such that u ∗ v = u .

A travel groupoid ( V, ∗ ) is said to be non-confusing if there is no confusing pair

in ( ).

Nebesky gave a characterization of non-confusing travel groupoids on a finite
graph.

V, ∗

V, ∗ G

Theorem 1 ([ 5 , Theorem 3]) . Let ( ) be a travel groupoid on a finite graph .

Then, ( V, ∗ ) is non-confusing if and only if, for all distinct elements u and v in V ,

k− 1 k

there exists a positive integer k such that the sequence ( u∗

0

v,...,u∗ v, u∗ v )

is a path from u to v in G .

Nebesky also showed a result on the existence of non-confusing travel groupoids.
Note that a travel groupoid (

V, ∗ ) is said to be simple if it satisfies the following

axiom (t3) if v ∗ u = u , then u ∗ ( v ∗ u )= u ∗ v (for all u, v ∈ V ).

Theorem 2 ([ 5 , Theorem 4]) . For every finite connected graph G , there exists

a simple non-confusing travel groupoid on G .

By Theorem 2 , we know that every finite connected graph has always at least
one non-confusing travel groupoid.
In this note, we study non-confusing travel groupoids on a given finite con-
nected graph and we give a one-to-one correspondence between the set of all
non-confusing travel groupoids on a finite connected graph and a combinatorial
structure in terms of the given graph.

2M inR sut

To describe the structure of non-confusing travel groupoids on a graph, we define
the following.