# Bus route

Thu Oct 4 03:19:36 CEST 2007

```    Hello Seqfans.
I considered about "Bus route problem".

If we made bus routes on a graph G, the roots should satisfy the following conditions.

1. One and only one route exists on all edges of G
2. Terminals of two different routes don't meet on the same point

This definition is equivalence with "Partition of graph G into strokes" without direction.
It is defined as follows.

Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii)union of corresponding undirected paths is E.

So, the case of undirected paths is the following.

Given an undirected graph G=(V,E), its partition into strokes is a collection of edge-disjoint paths (viewed as sets of edges) on V such that (i) union of any two paths is not a path; (ii)union of paths is E.

I wanted to know the numbers of "Bus routes" on n x n grid graphs.
._._._._.
|_|_|_|_|    n=4
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|

But it is too difficult to calculate by hand, so I count the case of 1 x n.
._._._._.
|_|_|_|_|

S : 1,4,14,46
off set = 0

I wonder if no mathematician have thought this problem.

Yasutoshi

```