|
| |
|
|
A373436
|
|
Triangle read by rows: T(n,k) is the sum of domination numbers of spanning subgraphs with k edges in the n-cycle graph.
|
|
2
|
|
|
|
1, 1, 2, 2, 1, 3, 6, 3, 1, 4, 12, 12, 8, 2, 5, 20, 30, 25, 10, 2, 6, 30, 60, 66, 42, 12, 2, 7, 42, 105, 147, 126, 63, 21, 3, 8, 56, 168, 288, 312, 216, 96, 24, 3, 9, 72, 252, 513, 675, 594, 351, 135, 27, 3, 10, 90, 360, 850, 1320, 1410, 1050, 540, 180, 40, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
From A365327(domination number k replaced by m, function T replaced by F) we have the average domination number given by (Sum_{m=1..n} m*F(n,m))/2^n.
In this case, each subgraph has the same probability, or each edge in the subgraph has a probability of occurrence p = 0.5.
The probability of the subgraph with k edges, where the occurrence of the edge has a probability p is p^k*(1-p)^(n-k).
If we want to vary with this probability and calculate the average value of the domination number, then we have to split the subgraphs according to the number of edges.
By this probability, we weigh the domination number over all subgraphs and then the average domination number is given by Sum_{k=0..n} (p^k*(1-p)^(n-k)*(Sum_{m=1..n} m*F(n,m,k))).
Here F(n,m,k) is a number of subgraphs of the n-cycle graph with k edges and domination number m.
So we need a three-dimensional table for the numbers of subgraphs now.
We can reduce this dimensionality by precalculating the sum of domination numbers of spanning subgraphs with k edges in the n-cycle graph.
Now we get E(n,p) = Sum_{k=0..n} (p^k*(1-p)^(n-k)*(T(n,k))), where T(n,k) = Sum_{m=1..n} m*F(n,m,k).
We used R package Ryacas to simplify equations for each n, see the FORMULA.
Also, we can conclude (Sum_{m=1..n} m*F(n,m))/2^n = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n for p = 0.5.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = n for k = 0.
T(n,k) = n*(T(n-1,k)+T(n-1,k-1))/(n-1) for 0 < k < n-1.
T(n,k) = n*ceiling(n/3) for k = n-1.
T(n,k) = ceiling(n/3) for k = n.
Average value of the domination number E(n,p) = Sum_{k=0..n} (p^k*(1-p)^(n-k)*(T(n,k))).
E(1,p) = 1*p^0*(1-p)^1 + 1*p^1*(1-p)^0 = 1 - 1*p + p^1 = 1.
E(2,p) = 2*p^0*(1-p)^2 + 2*p^1*(1-p)^1 + 1*p^2*(1-p)^0 = 2 - 2*p + p^2.
E(3,p) = 3*p^0*(1-p)^3 + 6*p^1*(1-p)^2 + 3*p^2*(1-p)^1 + 1*p^3*(1-p)^0 = 3 - 3*p + p^3.
E(4,p) = 4*(1-p)^4 + 12*p*(1-p)^3 + 12*p^2*(1-p)^2 + 8*p^3*(1-p) + 2*p^4 = 4 - 4*p + 4*p^3 - 4*p^4 + 2*p^4.
E(5,p) = 5 - 5*p + 5*p^3 - 5*p^4 + 2*p^5.
E(6,p) = 6 - 6*p + 6*p^3 - 6*p^4 + 2*p^6.
E(7,p) = 7 - 7*p + 7*p^3 - 7*p^4 + 7*p^6 - 7*p^7 + 3*p^7.
E(8,p) = 8 - 8*p + 8*p^3 - 8*p^4 + 8*p^6 - 8*p^7 + 3*p^8.
E(9,p) = 9 - 9*p + 9*p^3 - 9*p^4 + 9*p^6 - 9*p^7 + 3*p^9.
E(10,p) = 10 - 10*p + 10*p^3 - 10*p^4 + 10*p^6 - 10*p^7 + 10*p^9 - 10*p^10 + 4*p^10.
We can see a pattern:
E(n,p) = n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) - n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) + ceiling(n/3)*p^n.
n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) = n*(1-p^(3*ceiling(n/3)))/(1-p^3) = n*(1-p^(3*ceiling(n/3)))/((1-p)*(p^2+p+1)).
n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) = n*p*(1-p^(3*ceiling(n/3)))/((1-p)*(p^2+p+1)).
n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i)) - n*(Sum_{i=0..ceiling(n/3)-1} p^(3*i+1)) = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1).
E(n,p) = n*(1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n.
E(n,p) = n for p = 0.
E(n,p) = ceiling(n/3) for p = 1.
Relative average domination number:
E'(n,p) = E(n,p)/n.
E'(n,p) = (1-p^(3*ceiling(n/3)))/(p^2+p+1) + ceiling(n/3)*p^n/n.
Limit_{n->oo} E'(n,p) = lim_{n->oo} (1-p^(3*ceiling(n/3)))/(p^2+p+1) + lim_{n->oo} ceiling(n/3)*p^n/n = 1/(p^2+p+1).
Limit_{n->oo} E'(n,0) = 1.
Limit_{n->oo} E'(n,0.5) = 4/7.
Limit_{n->oo} E'(n,1) = 1/3.
|
|
|
EXAMPLE
|
Example of spanning subgraphs of cycle with 2 vertices:
Domination number: 2 1 1 1
/\ /\
. . . . . . . .
\/ \/
Number of edges: 0 1 1 2
Number of spanning subgraphs with k edges and domination number m in cycle with n = 3 vertices:
k\m 1 2 3
0 0 0 1
1 0 3 0
2 3 0 0
3 1 0 0
T(3,k) = Sum_{m=1..3} m*F(3,m,k)
T(3,0) = 3, T(3,1) = 6, T(3,2) = 3, T(3,3) = 1
The triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
1: 1 1
2: 2 2 1
3: 3 6 3 1
4: 4 12 12 8 2
5: 5 20 30 25 10 2
6: 6 30 60 66 42 12 2
7: 7 42 105 147 126 63 21 3
8: 8 56 168 288 312 216 96 24 3
9: 9 72 252 513 675 594 351 135 27 3
10: 10 90 360 850 1320 1410 1050 540 180 40 4
11: 11 110 495 1331 2387 3003 2706 1749 792 242 44 4
12: 12 132 660 1992 4056 5880 6228 4860 2772 1128 312 48 4
|
|
|
MATHEMATICA
|
A373436[n_, k_] := A373436[n, k] = Which[k == 0, n, k < n-1, n*(A373436[n-1, k] + A373436[n-1, k-1])/(n-1), True, Ceiling[n/3]*If[k == n, 1, n]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
