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

The Non-confusing Travel Groupoids
on a Finite Connected Graph

B

Jung Rae Cho 1 , Jeongmi Park 1(

) , and Yoshio Sano 2

1 Department of Mathematics, Pusan National University, Busan 609-735, Korea
{ jungcho,jm1015 } @pusan.ac.kr
2 Division of Information Engineering, Faculty of Engineering,
Information and Systems, University of Tsukuba, Ibaraki 305-8573, Japan
[e-mail]

Abstract. The notion of travel groupoids was introduced by L. Nebesky
in 2006 in connection with a study on geodetic graphs. A travel groupoid
is a pair of a set V and a binary operation on V satisfying two axioms.

For a travel groupoid, we can associate a graph. We say that a graph G
has a travel groupoid if the graph associated with the travel groupoid
is equal to G . A travel groupoid is said to be non-confusing if it has no
confusing pairs. Nebesky showed that every finite connected graph has
at least one non-confusing travel groupoid.
In this note, we study non-confusing travel groupoids on a given finite
connected 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.

∗

· ·

Keywords: Travel groupoid Confusing pair Non-confusing travel

· ·

groupoid Spanning tree

2010 Mathematics Subject Classification: 20N02, 05C12, 05C05.

Geodetic graph

1 Introduction

V, ∗ V ∗

A groupoid is the pair ( ) of a nonempty set and a binary operation on

V

. The notion of travel groupoids was introduced by L. Nebesk´y[ 5 ] in 2006
in connection with his study on geodetic graphs [ 1 - 3 ] and signpost systems [ 4 ].
First, let us recall the definition of travel groupoids.
A travel groupoid is a groupoid ( V, ∗ ) satisfying the following axioms (t1)

and (t2):

(t1) ( u ∗ v ) ∗ u = u (for all u, v ∈ V ),

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

Jung Rae Cho—This research was supported for two years by Pusan National Uni-
versity Research Grant.
Yoshio Sano—This work was supported by JSPS KAKENHI grant number 25887007.