cp's OEIS Frontend

A335807 Number of vertices in the n-th simplex graph of the complete graph on three vertices (K_3).

%I A335807 #77 Jun 23 2022 20:26:02
%S A335807 3,8,21,54,140,365,954,2496,6533,17102,44772,117213,306866,803384,
%T A335807 2103285,5506470,14416124,37741901,98809578,258686832,677250917,
%U A335807 1773065918,4641946836,12152774589,31816376930,83296356200,218072691669,570921718806,1494692464748,3913155675437
%N A335807 Number of vertices in the n-th simplex graph of the complete graph on three vertices (K_3).
%C A335807 The simplex k(G) of an undirected graph G is itself a graph that has one vertex for each clique in G. Two vertices are connected by an edge in k(G) if their corresponding cliques differ by the presence or absence of a single vertex in G. For the purposes of finding a simplex graph, the empty set of zero vertices is considered a 0-clique in G, and each individual vertex in G is considered a 1-clique in G.
%C A335807 If we define the simplex graph of a graph G to be k(G), then we can define the 2nd simplex graph to be k(k(G)), which is the simplex of the simplex of the graph G, and the 3rd simplex graph to be k(k(k(G))), and so on. We can also define the 0th simplex graph to be the graph itself.
%C A335807 Using recurrence relations and the initial values for order and size of the 1st simplex graph of a graph G, it is possible to calculate the orders (and sizes) of the n-th simplex graphs using an algorithm, which I provided as a JavaScript program.
%C A335807 The order, |V|(n), of the n-th simplex graph of a graph G follows this recurrence relation: |V|(n) = |V|(n - 1) + |E|(n - 1) + 1, where |E|(n - 1) is the size of the (n-1)-th simplex graph of G and |V|(n-1) is the order of the (n-1)-th simplex graph of G.
%C A335807 The size, |E|(n), of the n-th simplex graph of a graph G follows this recurrence relation: |E|(n) = |V|(n - 1) + 2*|E|(n - 1), where |V|(n-1) is the order of the (n-1)-th simplex graph of G and |E|(n-1) is the size of the (n-1)-th simplex graph of G.
%H A335807 Wikipedia, <a href="https://en.wikipedia.org/wiki/Simplex_graph">Simplex Graph</a>
%H A335807 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,1).
%F A335807 From _Colin Barker_, Aug 15 2020: (Start)
%F A335807 G.f.: (3 - 4*x + x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2)).
%F A335807 a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) for n>3.
%F A335807 (End)
%F A335807 a(n) = (10 + (5 - 11*sqrt(5))*(1/2*(3 - sqrt(5)))^n + (1/2*(3 + sqrt(5)))^n*(5 + 11*sqrt(5)))/10 for n > 0. - _Stefano Spezia_, Aug 15 2020
%F A335807 a(n) = 3*a(n-1) - a(n-2) - 1 for n >= 3. - _James Turbett_, Aug 18 2020
%F A335807 a(n) = 1+A055267(n), n>0. - _R. J. Mathar_, Mar 06 2022
%e A335807 The simplex graph of K_3 will have 8 vertices: 1 for the 0-clique in K_3, 3 for the 1-cliques in K_3, 3 for the 2-cliques in K_3, and 1 for the 3-clique in K_3.
%e A335807 It also has size 12. In the simplex graph, each vertex corresponding to a 1-clique in K_3 links to the simplex graph vertex corresponding to a 0-clique in K_3, creating 3 edges. Also, each simplex graph vertex corresponding to a 2-clique in K_3 links to 2 simplex graph vertices corresponding to a 1-clique in K_3, producing 6 more edges. Finally, the single vertex in the simplex graph corresponding to the 3-clique in K_3 links to each simplex graph vertex corresponding to a 2-clique in K_3, producing 3 more edges, for a total of 12 edges in the 1st simplex graph of K_3.
%e A335807 Using the recurrence relation, we can calculate |V|(2) = |V|(1) + |E|(1) + 1 = 8 + 12 + 1 = 21. Therefore, the 2nd simplex graph of K_3 will have 21 vertices.
%o A335807 (JavaScript)
%o A335807 //Define order and size of 1st simplex graph of K_3
%o A335807 var order = [8]
%o A335807 var size = [12]//Calculate the orders of the 1st through (numberOfTerms + 1)th simplex graphs of K_3
%o A335807 function simplexSequenceOrder (numberOfTerms) {
%o A335807 for (var i = 1; i <= numberOfTerms; i++) {
%o A335807 order[i] = order[i-1] + size[i-1] + 1;
%o A335807 size [i] = order[i-1] + 2*size[i-1];
%o A335807 }
%o A335807 return order.join();
%o A335807 }
%o A335807 (PARI) Vec((3 - 4*x + x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2)) + O(x^28)) \\ _Colin Barker_, Aug 16 2020
%K A335807 nonn,easy
%O A335807 0,1
%A A335807 _James Turbett_, Aug 14 2020