A245519 Number of alpha-labeled graphs with n edges and at most n vertices.
0, 0, 0, 2, 10, 64, 336, 1872, 11104, 71944, 508032, 3511232, 27192704, 223750464, 1947253504, 17899536448, 173156535168, 1760383827776, 18752453106176, 209034916385472, 2432351796434560, 29509268795249700
Offset: 1
Examples
For n=4, a(4)=2, there are 2 alpha-labeled graphs with 4 edges and at most 4 vertices. For n=10, a(10)=71944, there are 71944 alpha-labeled graphs with 10 edges and at most 10 vertices.
Links
- Christian Barrientos, Sarah Minion, On the number of alpha-labeled graphs, Discussiones Mathematicae Graph Theory, to appear.
- J. A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., (2013), #DS6.
- David A. Sheppard, The factorial representation of major balanced labelled graphs, Discrete Math., 15(1976), no. 4, 379-388.
Formula
a(n) = Sum_{L=1..n-2} Sum_{i=1..n-1} Product_{k=1..n} d(L,k,i), where
for i < L,
d(L,k) if 1 <= k <= i,
d(L,k,i) ={ d(L,k) - 1 if i < k < n - i,
d(L,k) if n - i <= k <= n;
for i > L + 1,
d(L,k) if 1 <= k <= n - i,
d(L,k,i) ={ d(L,k) - 1 if n - i < k < n - i + L + 2,
d(L,k) if n - i + L + 2 <= k <= n.
k if 1 <= k < m,
d(L,k) ={ L + 1 if m <= k <= M,
n + 1 - k if M < k <= n,
m = min{L + 1, n - L}, M = max{L + 1, n - L}.