

A335807


Number of vertices in the nth 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 0clique in G, and each individual vertex in G is considered a 1clique 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 nth simplex graphs using an algorithm, which I provided as a JavaScript program.
The order, V(n), of the nth 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 (n1)th simplex graph of G and V(n1) is the order of the (n1)th simplex graph of G.
The size, E(n), of the nth simplex graph of a graph G follows this recurrence relation: E(n) = V(n  1) + 2*E(n  1), where V(n1) is the order of the (n1)th simplex graph of G and E(n1) is the size of the (n1)th simplex graph of G.


LINKS



FORMULA

G.f.: (3  4*x + x^2  x^3) / ((1  x)*(1  3*x + x^2)).
a(n) = 4*a(n1)  4*a(n2) + a(n3) 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(n1)  a(n2)  1 for n >= 3.  James Turbett, Aug 18 2020


EXAMPLE

The simplex graph of K_3 will have 8 vertices: 1 for the 0clique in K_3, 3 for the 1cliques in K_3, 3 for the 2cliques in K_3, and 1 for the 3clique in K_3.
It also has size 12. In the simplex graph, each vertex corresponding to a 1clique in K_3 links to the simplex graph vertex corresponding to a 0clique in K_3, creating 3 edges. Also, each simplex graph vertex corresponding to a 2clique in K_3 links to 2 simplex graph vertices corresponding to a 1clique in K_3, producing 6 more edges. Finally, the single vertex in the simplex graph corresponding to the 3clique in K_3 links to each simplex graph vertex corresponding to a 2clique 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[i1] + size[i1] + 1;
size [i] = order[i1] + 2*size[i1];
}
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



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



