login
The overall first Zagreb index of the rooted tree having Matula-Goebel number n.
10

%I #14 Mar 07 2017 11:25:23

%S 0,2,10,10,28,28,36,36,60,60,60,80,80,80,110,112,80,158,112,146,146,

%T 110,158,222,182,158,294,196,146,266,110,320,182,146,238,414,222,222,

%U 266,370,158,354,196,238,472,294,266,594,312,424,238,354,320,744,280,494,370,266,146,660,414,182,624

%N The overall first Zagreb index of the rooted tree having Matula-Goebel number n.

%C The overall first Zagreb index of any simple connected graph G is defined as the sum of the first Zagreb indices of all the subgraphs of G. The first Zagreb index of a simple connected graph is the sum of the squared degrees of its vertices.

%C 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.

%D D. Bonchev and N. Trinajstic, Overall molecular descriptors. 3. Overall Zagreb indices, SAR and QSAR in Environmental Research, 12, 2001, 213-236.

%D F. Goebel, On a 1-1 correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.

%D I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.

%D I. Gutman and Y-N. Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.

%D D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.

%H E. Deutsch, <a href="http://arxiv.org/abs/1111.4288"> Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288.

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%F A198339(n) gives the sequence of the Matula-Goebel numbers of all the subtrees of the rooted tree with Matula-Goebel number n. A196053(k) is the first Zagreb index of the rooted tree with Matula-Goebel number k.

%e a(3)=10 because the rooted tree with Matula-Goebel number 3 is the path tree with 3 vertices R - A - B; the subtrees are R, A, B, RA, AB, and RAB with first Zagreb indices 0, 0, 0, 2, 2, and 6, respectively.

%p with(numtheory); Z1 := 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 0 elif bigomega(n) = 1 then Z1(pi(n))+2+2*bigomega(pi(n)) else Z1(r(n))+Z1(s(n))-bigomega(r(n))^2-bigomega(s(n))^2+bigomega(n)^2 end if end proc; m2union := proc (x, y) sort([op(x), op(y)]) end proc; with(numtheory); MRST := 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, seq(ithprime(mrst[pi(n)][i]), i = 1 .. nops(mrst[pi(n)]))] else [seq(seq(mrst[r(n)][i]*mrst[s(n)][j], i = 1 .. nops(mrst[r(n)])), j = 1 .. nops(mrst[s(n)]))] end if end proc; MNRST := 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 [] elif bigomega(n) = 1 then m2union(mrst[pi(n)], mnrst[pi(n)]) else m2union(mnrst[r(n)], mnrst[s(n)]) end if end proc; MST := proc (n) m2union(mrst[n], mnrst[n]) end proc; for n to 2000 do mrst[n] := MRST(n); mnrst[n] := MNRST(n); mst[n] := MST(n) end do; OZ1 := proc (n) options operator, arrow; add(Z1(MST(n)[j]), j = 1 .. nops(MST(n))) end proc; seq(OZ1(n), n = 1 .. 120); # MRST considers the subtrees that contain the root; MNRST considers the subtrees that do not contain the root; MST considers all subtrees.

%Y Cf. A198339, A196053, A212618, A212619, A212620, A212622, A212623, A212624, A212625, A212626, A212627, A212628, A212629, A212630, A212631, A212632.

%K nonn

%O 1,2

%A _Emeric Deutsch_, Jun 01 2012