A206490 The eccentric connectivity index of the rooted tree with Matula-Goebel number n.

0, 2, 6, 6, 14, 14, 9, 9, 24, 24, 24, 19, 19, 19, 38, 12, 19, 29, 12, 31, 31, 38, 29, 24, 54, 29, 36, 24, 31, 45, 38, 15, 54, 31, 47, 34, 24, 24, 45, 38, 29, 36, 24, 47, 54, 36, 45, 29, 38, 61, 47, 36, 15, 41, 74, 29, 38, 45, 31, 52, 34, 54, 43, 18, 63, 63, 24, 38, 54, 54, 38, 39, 36, 34, 70, 29, 65, 52

Offset: 1

Author

Emeric Deutsch, May 08 2012

Keywords

• nonn

Comments

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 eccentric connectivity index of a simple connected graph G is defined as the sum over all vertices i of G of the product E(i) D(i), where E(i) is the eccentricity and D(i) is the degree of vertex i.

Examples

			a(7)=9 because the rooted tree with Matula-Goebel number 7 is Y; the 3 pendant vertices have degree 1 and eccentricity 2 and the 4th vertex has degree 3 and eccentricity 1; 1*2 + 1*2 + 1*2 + 3*1 = 9.
		

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 Y-N. 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.
• V. Sharma, R. Goswami, and A. K. Madan, Eccentric Connectivity index: a novel highly discriminating topological descriptor for structure-property and structure-activity studies, J. Chem. Inf. Comput. Sci., 37, 1997, 273-282.

Links

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

Programs

Maple

with(numtheory): 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, dt, drs: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: dt := proc (i, j) if i = 1 and j = 1 then 0 elif i = 1 and 1 < j then 1+dd[pi(n)][1, j-1] elif 1 < i and j = 1 then 1+dd[pi(n)][i-1, 1] elif 1 < i and 1 < j then dd[pi(n)][i-1, j-1] else  end if end proc: drs := proc (i, j) if 1 <= i and 1 <= j and i <= V(r(n)) and j <= V(r(n)) then dd[r(n)][i, j] elif 1+V(r(n)) <= i and 1+V(r(n)) <= j and i <= V(n) and j <= V(n) then dd[s(n)][i-V(r(n))+1, j-V(r(n))+1] elif 1 <= i and i <= V(r(n)) and 1+V(r(n)) <= j and j <= n then dd[r(n)][i, 1]+dd[s(n)][1, j-V(r(n))+1] else dd[r(n)][1, j]+dd[s(n)][i-V(r(n))+1, 1] end if end proc: if n = 1 then Matrix(1, 1, [0]) elif bigomega(n) = 1 then Matrix(V(n), V(n), dt) else Matrix(V(n), V(n), drs) end if end proc: for n to 1000 do dd[n] := d(n) end do: > a := proc (n) local ddd, aa: ddd := proc (n) options operator, arrow: d(n) end proc: aa := proc (i, j) if ddd(n)[i, j] = 1 then 1 else 0 end if end proc: Matrix(RowDimension(ddd(n)), RowDimension(ddd(n)), aa) end proc: > RS := proc (m) local dim: dim := RowDimension(m): Matrix(1, dim, [seq(add(m[i, j], j = 1 .. dim), i = 1 .. dim)]) end proc: > MX := proc (m) local dim: dim := RowDimension(m): Matrix(1, dim, [seq(max(seq(m[i, j], j = 1 .. dim)), i = 1 .. dim)]) end proc: > ECI := proc (n) options operator, arrow: MatrixMatrixMultiply(RS(a(n)), Transpose(MX(d(n))))[1, 1] end proc: seq(ECI(n), n = 1 .. 77);

Formula

Explanation of the Maple program: "V" finds recursively the number of vertices (needed later); "d" finds recursively the distance matrix; "a" finds the adjacency matrix from the distance matrix; "RS" finds the vector of the row sums of any matrix (will be applied to the adjacency matrix to yield the vertex degrees); "MX" finds the vector of the largest row entries of any matrix (will be applied to the distance matrix to yield the vertex eccentricities); "ECI" finds the eccentric connectivity index by taking the dot product of the two vectors just mentioned.