login
The Wiener index of the graph obtained by applying Mycielski's construction to the crown graph G(n) (n>=3).
0

%I #16 May 28 2018 06:03:54

%S 141,240,365,516,693,896,1125,1380,1661,1968,2301,2660,3045,3456,3893,

%T 4356,4845,5360,5901,6468,7061,7680,8325,8996,9693,10416,11165,11940,

%U 12741,13568,14421,15300,16205,17136,18093,19076,20085,21120

%N The Wiener index of the graph obtained by applying Mycielski's construction to the crown graph G(n) (n>=3).

%C The crown graph G(n) is the graph with vertex set {x(1), x(2), ...x(n), y(1), y(2), ..., y(n)} and edge set {(x(i), y(j)): 1<=i,j<=n, i != j} (= the complete bipartite graph K(n,n) with horizontal edges removed).

%C The value a(4)=240 has been checked by the direct computation of the distance matrix of the Mycielskian of G(4) (via Maple).

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

%H R. Balakrishnan, S. F. Raj, <a href="http://dx.doi.org/10.7151/dmgt.1509">The Wiener number of powers of the Mycielskian</a>, Discussiones Math. Graph Theory, 30, 2010, 489-498 (see Theorem 2.1).

%H B. E. Sagan, Y-N. Yeh and P. Zhang, <a href="http://dx.doi.org/10.1002/(SICI)1097-461X(1996)60:5&lt;959::AID-QUA2&gt;3.0.CO;2-W">The Wiener Polynomial of a Graph</a>, Internat. J. of Quantum Chem., 60, 1996, 959-969.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

%F a(n) = 13*n^2 + 8*n.

%F G.f.: x^3*(141-183*x+68*x^2)/(1-x)^3.

%p a := proc (n) options operator, arrow: 13*n^2+8*n end proc: seq(a(n), n = 3 .. 40);

%o (PARI) a(n)=13*n^2+8*n \\ _Charles R Greathouse IV_, Jun 17 2017

%Y Cf. A033428.

%K nonn,easy

%O 3,1

%A _Emeric Deutsch_, Aug 29 2013