login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A206486 The total walk count in the rooted tree with Matula-Goebel number n. 0
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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

Table of n, a(n) for n=1..55.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.

Index entries for sequences related to Matula-Goebel numbers

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.

EXAMPLE

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.

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);

CROSSREFS

Cf. A193403.

Sequence in context: A168381 A212621 A156780 * A067046 A066394 A232500

Adjacent sequences:  A206483 A206484 A206485 * A206487 A206488 A206489

KEYWORD

nonn

AUTHOR

Emeric Deutsch, Feb 20 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 16:40 EST 2019. Contains 319271 sequences. (Running on oeis4.)