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,1

Comments

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.

Links

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.

Formula

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.

Example

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

Crossrefs

Row sums are A000079.

Column sums are A002063(k-1).

Sequence in context: A120873 A125161 A331791 * A125933 A255054 A011857

Adjacent sequences: A365324 A365325 A365326 * A365328 A365329 A365330

Keyword

nonn,tabl

Author

Roman Hros, Sep 01 2023

Status

approved