A193402 The Matula-Göbel numbers of the rooted trees such that 2 is an eigenvalue of the Laplacian matrix.
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
Offset: 1
Keywords
Examples
5 is in the sequence because the rooted tree with Matula-Gö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(x-2)(x^2 -4x +2).
Links
- E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
- Yi-zheng Fan, On the eigenvalue two and matching number of a tree, Acta Math. Appl. Sinica, English Series, 20, 2004, 257-262.
- F. Göbel, 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. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
- Index entries for sequences related to Matula-Goebel numbers
Programs
-
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)][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 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;
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 Matula-Göbel numbers 1..1000 (upper limit can be altered), then switches (easily) to the Laplacian matrices and finds their characteristic polynomials.
Comments