login
a(n)/A002939(n+1) is the Kirchhoff index of the disjoint union of two complete graphs each on n and n+1 vertices with the empty graph on n+1 vertices.
1

%I #17 Nov 10 2020 23:17:54

%S 2,77,334,881,1826,3277,5342,8129,11746,16301,21902,28657,36674,46061,

%T 56926,69377,83522,99469,117326,137201,159202,183437,210014,239041,

%U 270626,304877,341902,381809,424706,470701,519902

%N a(n)/A002939(n+1) is the Kirchhoff index of the disjoint union of two complete graphs each on n and n+1 vertices with the empty graph on n+1 vertices.

%C Equivalently, the graph can be described as the graph on 3*n + 2 vertices with labels 0..3*n+1 and with i and j adjacent iff i+j>0 mod 3.

%C These graphs are cographs.

%C The initial term a(0) = 2 has been included to agree with the formula. For the graph, is not defined.

%H H-Y. Ching, R. Florez, and A. Mukherjee, <a href="https://arxiv.org/abs/2009.02770">Families of Integral Cographs within a Triangular Arrays</a>, arXiv:2009.02770 [math.CO], 2020.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KirchhoffIndex.html">Kirchhoff Index</a>

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

%F a(n) = 18*n^3 + 37*n^2 + 20*n + 2.

%F G.f.: (2 + 69*x + 38*x^2 - x^3)/(x - 1)^4.

%F E.g.f.: exp(x)*(2 + 75*x + 91*x^2 + 18*x^3). - _Stefano Spezia_, Nov 08 2020

%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - _Wesley Ivan Hurt_, Nov 08 2020

%e The adjacency matrix of the graph associated with n = 2 is:

%e [0, 1, 0, 0, 0, 1, 1, 1]

%e [1, 0, 0, 0, 0, 1, 1, 1]

%e [0, 0, 0, 1, 1, 1, 1, 1]

%e [0, 0, 1, 0, 1, 1, 1, 1]

%e [0, 0, 1, 1, 0, 1, 1, 1]

%e [1, 1, 1, 1, 1, 0, 0, 0]

%e [1, 1, 1, 1, 1, 0, 0, 0]

%e [1, 1, 1, 1, 1, 0, 0, 0].

%e a(2) = 334 because the Kirchhoff index of the graph is 334/30=334/A002939(3).

%e The first few Kirchhoff indices (n >= 1) as reduced fractions are 77/12, 167/15, 881/56, 913/45, 3277/132, 2671/91, 8129/240, 5873/153, 16301/380, 10951/231.

%t Table[(18n^3+37n^2+20n+2), {n,0,30}]

%Y Cf. A338527, A338104, A338109.

%K nonn,easy

%O 0,1

%A _Rigoberto Florez_, Nov 07 2020