|
| |
|
|
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
|
|
|
|
FORMULA
|
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
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
