A206486 The total walk count in the rooted tree with Matula-Goebel number n.

0, 2, 10, 10, 32, 32, 36, 36, 88, 88, 88, 106, 106, 106, 222, 140, 106, 284, 140, 268, 268, 222, 284, 370, 536, 284, 756, 330, 268, 708, 222, 490, 536, 268, 658, 1052, 370, 370, 708, 978, 284, 872, 330, 658, 1856, 756, 708, 1542, 798, 1712, 658, 872, 490, 2882, 1254

Offset: 1

Author

Emeric Deutsch, Feb 20 2012

Keywords

• nonn

Comments

The total walk count in a graph with n vertices is obtained by counting all walks of lengths 1,2,...,n-1. Some authors define it as 1/2 of the above.

The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.

The Maple program yields a(n) by using the command TWC(n).

Examples

			a(3)=10 because the rooted tree with Matula-Goebel number 3 is the path a-b-c on 3 vertices and the walks are: ab, ba, bc, cb, abc, cba, aba, bab, bcb, and cbc.
		

References

• F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
• I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
• I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
• D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
• G. Ruecker and C. Ruecker, Walk counts, labyrinthicity, and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci., 40, 2000, 99-106.
• G. Ruecker and C. Ruecker, Substructure, subgraph, and walk counts as measures of the complexity of graphs and molecules, J. Chem. Inf. Comput. Sci., 41, 2001, 1457-1462.
• D. Bonchev and G. A. Buck, Quantitative measures of network complexity, in: Complexity in Chemistry, Biology, and Ecology, Springer, New York, pp. 191-235.

Links

• E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.
• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Cf. A193403.

Programs

Maple

with(numtheory); with(linalg): with(LinearAlgebra): V := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then 1+V(pi(n)) else V(r(n))+V(s(n))-1 end if end proc: d := proc (n) local r, s, C, a: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: C := proc (A, B) local c: c := proc (i, j) options operator, arrow: A[1, i]+B[1, j+1] end proc: Matrix(RowDimension(A), RowDimension(B)-1, c) end proc: a := proc (i, j) if i = 1 and j = 1 then 0 elif 2 <= i and 2 <= j then dd[pi(n)][i-1, j-1] elif i = 1 then 1+dd[pi(n)][1, j-1] elif j = 1 then 1+dd[pi(n)][i-1, 1] else  end if end proc: if n = 1 then Matrix(1, 1, [0]) elif bigomega(n) = 1 then Matrix(V(n), V(n), a) else Matrix(blockmatrix(2, 2, [dd[r(n)], C(dd[r(n)], dd[s(n)]), Transpose(C(dd[r(n)], dd[s(n)])), SubMatrix(dd[s(n)], 2 .. RowDimension(dd[s(n)]), 2 .. RowDimension(dd[s(n)]))])) end if end proc: for n to 10000 do dd[n] := d(n) end do: DA := proc (d) local aa: aa := proc (i, j) if d[i, j] = 1 then 1 else 0 end if end proc: Matrix(RowDimension(d), RowDimension(d), aa) end proc: TWC := proc (n) options operator, arrow: add(add((sum(DA(d(n))^k, k = 1 .. V(n)-1))[i, j], j = 1 .. V(n)), i = 1 .. V(n)) end proc; seq(TWC(n), n = 1 .. 55);

Formula

In A193403 it is shown how to find the adjacency matrix of a rooted tree with a given Matula-Goebel number. It is well-known that the (i,j)-entry in the k-th power of the adjacency matrix of a graph G gives the number of walks of length k in G from vertex i to vertex j. The Maple program (improvable) is based on the above facts.