

A193402


The MatulaGöbel numbers of the rooted trees such that 2 is an eigenvalue of the Laplacian matrix.


2



2, 5, 6, 15, 18, 22, 23, 26, 31, 41, 45, 54, 55, 65, 66, 69, 78, 93, 94, 103, 122, 123, 135, 137, 158, 162, 165, 166, 167, 195, 198, 202, 207, 211, 234, 235, 242, 253, 254, 279, 282, 283, 286, 299, 305, 309, 338, 341, 343, 358, 366, 369, 394, 395, 401, 403
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

The MatulaGöbel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGöbel 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 MatulaGöbel numbers of the m branches of T.


LINKS

Table of n, a(n) for n=1..56.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
Yizheng Fan, On the eigenvalue two and matching number of a tree, Acta Math. Appl. Sinica, English Series, 20, 2004, 257262.
F. Göbel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

Let T be a rooted tree with root b. If b has degree 1, then let A be the rooted tree with root c, obtained from T by deleting the edge bc emanating from the root. If b has degree >=2, then A is obtained (not necessarily in a unique way) by joining at b two trees B and C, rooted at b. It is straightforward to express the distance matrix of T in terms of the entries of the distance matrix of A (resp. of B and C). Making use of this, the Maple program (improvable!) finds recursively the distance matrices of the rooted trees with MatulaGöbel numbers 1..1000 (upper limit can be altered), then switches (easily) to the Laplacian matrices and finds their characteristic polynomials.


EXAMPLE

5 is in the sequence because the rooted tree with MatulaGöbel number 5 is the path on 4 vertices; the Laplacian matrix is [1,1,0,0; 1,2,1,0; 0,1,2,1;0,0,1,1] with characteristic polynomial x(x2)(x^2 4x +2).


MAPLE

with(numtheory): with(linalg): with(LinearAlgebra): 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: AL := proc (a) local ll: ll := proc (i, j) if i = j then add(a[i, k], k = 1 .. RowDimension(a)) else a[i, j] end if end proc: Matrix(RowDimension(a), RowDimension(a), ll) end proc: 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)][i1, j1] elif i = 1 then 1+dd[pi(n)][1, j1] elif j = 1 then 1+dd[pi(n)][i1, 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 1000 do dd[n] := d(n) end do: S := {}: for n to 500 do if subs(x = 2, CharacteristicPolynomial(AL(DA(d(n))), x)) = 0 then S := `union`(S, {n}) else end if end do: S;


CROSSREFS

Cf. A061775, A184187, A193403, A193401.
Sequence in context: A205385 A287203 A291211 * A193405 A037079 A101325
Adjacent sequences: A193399 A193400 A193401 * A193403 A193404 A193405


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Feb 11 2012


STATUS

approved



