A228599 The Wiener index of the graph obtained by applying Mycielski's construction to the rooted tree having Matula-Goebel number n.

5, 15, 33, 33, 62, 62, 59, 59, 103, 103, 103, 99, 99, 99, 156, 93, 99, 151, 93, 152, 152, 156, 151, 144, 221, 151, 215, 147, 152, 216, 156, 135, 221, 152, 217, 207, 144, 144, 216, 209, 151, 211, 147, 217, 292, 215, 216, 197, 213, 293, 217, 211

Offset: 1

Author

Emeric Deutsch, Aug 29 2013

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.

a(2^n) = A228318(n). Indeed, the rooted tree corresponding to the Matula-Goebel number 2^n is the star graph K(1,n).

a(A007097(n)) = A228321(n). Indeed, A007097(n) for n=1,2,... yields the primeth recurrence sequence (A007097(1)=2, A007097(n+1)=A007097(n)-th prime; first few terms are 2,3,5,11,31,127,709). The corresponding rooted trees are the path trees on n+1 vertices.

References

• D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 205.

Links

• R. Balakrishnan, S. F. Raj, The Wiener number of powers of the Mycielskian, Discussiones Math. Graph Theory, 30, 2010, 489-498 (see Theorem 2.1).
• E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Cf. A061775, A196050, A196059, A228318, A007097, A228321

Programs

Maple

with(numtheory): V := proc (n) local u, v: u := proc (n) options operator, arrow: op(1, factorset(n)) end proc: v := proc (n) options operator, arrow: n/u(n) end proc: if n = 1 then 1 elif isprime(n) then 1+V(pi(n)) else V(u(n))+V(v(n))-1 end if end proc: WP := proc (n) local r, s, R: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: R := proc (n) if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(x*R(pi(n))+x)) else sort(expand(R(r(n))+R(s(n)))) end if end proc: if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(WP(pi(n))+x*R(pi(n))+x)) else sort(expand(WP(r(n))+WP(s(n))+R(r(n))*R(s(n)))) end if end proc: p2 := proc (n) options operator, arrow: coeff(WP(n), x, 2) end proc: p3 := proc (n) options operator, arrow: coeff(WP(n), x, 3) end proc: a := proc (n) options operator, arrow: 6*V(n)^2-8*V(n)+7-4*p2(n)-p3(n) end proc: seq(a(n), n = 1 .. 80);

Formula

In Balakrishnan et al. one proves that the Wiener index of the Mycielskian of a connected graph G is 6V^2 - V - 7E - 4p(2) - p(3), where V is number of vertices of G, E is number of edges in G, and p(i) is number of pairs of vertices in G which are at distance i. For the rooted tree with Matula-Goebel number n these quantities can be found in A061775, A196050, and A196059.