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

%I #30 Oct 18 2022 15:02:04

%S 1,60,289,796,1689,3076,5065,7764,11281,15724,21201,27820,35689,44916,

%T 55609,67876,81825,97564,115201,134844,156601,180580,206889,235636,

%U 266929,300876,337585,377164,419721,465364,514201,566340,621889,680956,743649,810076,880345

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

%C Equivalently, the graph can be described as the graph on 3*n + 1 vertices with labels 0..3*n and with i and j adjacent iff A011655(i + j) = 1.

%C These graphs are cographs.

%C The initial term a(0) = 1 has been included to agree with the formula. For the graph, it should be 0.

%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) = 1 + 10*n + 31*n^2 + 18*n^3.

%F From _Stefano Spezia_, Oct 10 2020: (Start)

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

%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) for n >= 4. (End)

%e The adjacency matrix of the graph associated with n = 2 is: (compare A204437)

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

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

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

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

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

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

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

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

%e The first few Kirchhoff indices (n >= 1) as reduced fractions are 5, 289/30, 199/14, 563/30, 769/33, 5065/182, 647/20, 11281/306, 3931/95, 7067/154, 6955/138, 35689/650.

%t Table[1+10n+31n^2+18n^3,{n,30}]

%o (PARI) a(n)=1+10*n+31*n^2+18*n^3 \\ _Charles R Greathouse IV_, Oct 18 2022

%Y Cf. A002939, A011655, A204437, A338104.

%K nonn,easy

%O 0,2

%A _Rigoberto Florez_, Oct 10 2020