The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A335807 Number of vertices in the n-th simplex graph of the complete graph on three vertices (K_3). 0
 3, 8, 21, 54, 140, 365, 954, 2496, 6533, 17102, 44772, 117213, 306866, 803384, 2103285, 5506470, 14416124, 37741901, 98809578, 258686832, 677250917, 1773065918, 4641946836, 12152774589, 31816376930, 83296356200, 218072691669, 570921718806, 1494692464748, 3913155675437 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,1 COMMENTS 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. 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. 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. 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. 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. LINKS Table of n, a(n) for n=0..29. Wikipedia, Simplex Graph Index entries for linear recurrences with constant coefficients, signature (4,-4,1). FORMULA From Colin Barker, Aug 15 2020: (Start) G.f.: (3 - 4*x + x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2)). a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) for n>3. (End) 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 a(n) = 3*a(n-1) - a(n-2) - 1 for n >= 3. - James Turbett, Aug 18 2020 a(n) = 1+A055267(n), n>0. - R. J. Mathar, Mar 06 2022 EXAMPLE 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. 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. 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. PROG (JavaScript) //Define order and size of 1st simplex graph of K_3 var order = [8] var size = [12]//Calculate the orders of the 1st through (numberOfTerms + 1)th simplex graphs of K_3 function simplexSequenceOrder (numberOfTerms) { for (var i = 1; i <= numberOfTerms; i++) { order[i] = order[i-1] + size[i-1] + 1; size [i] = order[i-1] + 2*size[i-1]; } return order.join(); } (PARI) Vec((3 - 4*x + x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2)) + O(x^28)) \\ Colin Barker, Aug 16 2020 CROSSREFS Sequence in context: A135473 A242452 A190139 * A005580 A292619 A231222 Adjacent sequences: A335804 A335805 A335806 * A335808 A335809 A335810 KEYWORD nonn,easy AUTHOR James Turbett, Aug 14 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 9 11:50 EDT 2024. Contains 375042 sequences. (Running on oeis4.)