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

k k

( V, ∗ ) that u ∗ v = v and that ( u ∗

0

v,...,u∗ v ) is the path from u to v in T v .

0 k

Therefore, ( u∗ v,...,u∗ v ) is a path from u to v in G . By Theorem 1 , the travel

groupoid ( V, ∗ ) is non-confusing. Now, we define a map ʦ : ʠ v∈V S G ( v ) ₒN G by

ʦ(( T v ) v∈V )=( V, ∗ ), where ( V, ∗ ) is the non-confusing travel groupoid defined

as above for ( T v ) v∈V .

Next, let ( V, ∗ ) be a non-confusing travel groupoid on a finite connected

graph G .Foreach v ∈ V ( G ), we define a graph T v by V ( T v ):= V and E ( T v ):=

{{u, u ∗ v}|u ∈ V \{v}} . By Lemma 3 , T v is a v -tree of G , i.e., T v ∈S G ( v ).

Therefore, ( T v ) v∈V ∈ ʠ v∈V S G ( v ). Now, we define a map ʨ : N G ₒ ʠ v∈V S G ( v )

by ʨ(( V, ∗ )) = ( T v ) v∈V , where ( T v ) v∈V are v -trees defined as above for ( V, ∗ ).

Then, we can check that ʨ ⓦ ʦ(( T v ) v∈V )=( T v ) v∈V holds for any ( T v ) v∈V ∈

ʠ v∈V S G ( ∈N G .

Hence the map ʦ is a one-to-one correspondence between the sets ʠ v∈V S G (

v ) and that ʦ ⓦ ʨ(( V, ∗ )) = ( V, ∗ ) holds for any ( V, ∗ )

v )

and N G .

Corollary 5. Let be a finite connected graph. Then, the number of non-

confusing travel groupoids on

G

G is equal to ʠ v∈V ( G ) |S G ( v ) | .

Proof. It follows from Theorem 4 .

References

1. Nebesky, L.: An algebraic characterization of geodetic graphs. Czech. Math. J.
48 (123), 701-710 (1998)
2. Nebesky, L.: A tree as a finite nonempty set with a binary operation. Mathematica
Bohemica 125 , 455-458 (2000)
3. Nebesky, L.: New proof of a characterization of geodetic graphs. Czech. Math. J.
52 (127), 33-39 (2002)
4. Nebesky, L.: On signpost systems and connected graphs. Czech. Math. J. 55 (130),
283-293 (2005)
5. Nebesky, L.: Travel groupoids. Czech. Math. J. 56 (131), 659-675 (2006)