A373436 -id:A373436 - cp's OEIS frontend

A365327 Triangle read by rows: T(n,k) is the number of spanning subgraphs of the n-cycle graph with domination number k.

2, 3, 1, 4, 3, 1, 0, 11, 4, 1, 0, 11, 15, 5, 1, 0, 10, 26, 21, 6, 1, 0, 0, 43, 49, 28, 7, 1, 0, 0, 33, 98, 80, 36, 8, 1, 0, 0, 22, 126, 189, 120, 45, 9, 1, 0, 0, 0, 141, 322, 325, 170, 55, 10, 1, 0, 0, 0, 89, 462, 671, 517, 231, 66, 11, 1, 0, 0, 0, 46, 480, 1162, 1236, 777, 304, 78, 12, 1, 0, 0, 0, 0, 417, 1586, 2483, 2093, 1118, 390, 91, 13, 1

Offset: 1

Roman Hros, Sep 01 2023

For n >= 3 the n-cycle graph is a simple graph. In the case of n=1 the graph is a loop and for n=2 a double edge.
The number of spanning subgraphs of the n-cycle graph is given by 2^n which is also the sum of the n-th row Sum_{k=1..n} T(n,k).
The average domination number is given by (Sum_{k=1..n} k*T(n,k))/2^n.
The relative average domination number is given by ((Sum_{k=1..n} k*T(n,k))/2^n)/n.

			Example of spanning subgraphs of cycle with 2 vertices:
Domination number: 2      1      1      1
                          /\            /\
                  .  .   .  .   .  .   .  .
                                 \/     \/
The triangle T(n,k) begins:
n\k 1   2   3    4    5     6     7    8    9  10  11  12 ...
1:  2
2:  3   1
3:  4   3   1
4:  0  11   4    1
5:  0  11  15    5    1
6:  0  10  26   21    6     1
7:  0   0  43   49   28     7     1
8:  0   0  33   98   80    36     8    1
9:  0   0  22  126  189   120    45    9    1
10: 0   0   0  141  322   325   170   55   10   1
11: 0   0   0   89  462   671   517  231   66  11   1
12: 0   0   0   46  480  1162  1236  777  304  78  12   1

Roman Hros, Table of n, a(n) for n = 1..253 (Rows n = 1..22)
Roman Hros, Effective Enumeration of Selected Graph Characteristics, IIT.SRC 2020: 16th Student Research Conference in Informatics and Information Technologies.

Row sums are A000079.
Column sums are A002063(k-1).
Cf. A373436.

T(n,n) = 1 for n > 1.
T(n,n-1) = T(n-1, n-2) + 1 for n > 3.
T(n,n-2) = T(n-1, n-3) + T(n, n-1) for n > 5.
T(n,n-3) = T(n-1, n-4) + T(n, n-2) - 5 for n > 6.
T(n,n-4) = T(n-1, n-5) + T(n-1, n-4) + 11 + Sum_{i=1..n-9} (i+4) for n > 8.
G.f.:
For n > 3; G(n) = x*(G(n-1) + G(n-2) + 2*G(n-3)) + g(n); where
         2*(1-x)*x^(n/3)   for n mod 3 = 0.
g(n) = { 0                 for n mod 3 = 1.
         (1-x)*x^((n+1)/3) for n mod 3 = 2.
For n mod 3 = 0:
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) + 2 for k =  n/3.
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) - 2 for k =  n/3 + 1.
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1)     for k >= n/3 + 2.
For n mod 3 = 1:
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1)     for k >= (n+2)/3.
For n mod 3 = 2:
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) + 1 for k =  (n+1)/3.
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1) - 1 for k =  (n+1)/3 + 1.
T(n,k) = 2*T(n-3,k-1) + T(n-2,k-1) + T(n-1,k-1)     for k >= (n+1)/3 + 2.

cp's OEIS Frontend

A365327 Triangle read by rows: T(n,k) is the number of spanning subgraphs of the n-cycle graph with domination number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula