0,2

If we make bus routes on a graph G, the routes 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 equivalent to a "partition of graph G into undirected strokes". 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.

Definition. 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.

a(n) = Product_{v_i} m_i + Sum_{c_j} (se_j - 1)*(Product_{v_k E (G_n-c_j)} m_k - {number of partitions of (G_n-c_i) which has cycles}) where:

v_i E V_n, G_n={V_n,E_n}, "E" means element

m_i means number of matching of incident edges of v_i

c_j means cycles in G_n

se_j means number of start-end points in c_j

v_k E G_n and not(v_k E c_j)

m_k means number of matching of incident edges of v_k

If (G_n-c_j) is empty then Product_{v_k E (G_n-c_j)} m_k = 1.

a(n)=10*(a(n-1)-a(n-2))+4. - Max Alekseyev

Cf. A131518.

Adjacent sequences: A131706 A131707 A131708 this_sequence A131710 A131711 A131712

Sequence in context: A055913 A005757 A089508 this_sequence A139614 A068390 A008506

nonn

Yasutoshi Kohmoto (zbi74583(AT)boat.zero.ad.jp), Oct 03 2007, revised Nov 20 2007