OFFSET
1,13
COMMENTS
A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation Psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with at most k parts. This sequence gives A(n,k) = Psi_k(P_n), i.e., the number of non-equivalent distinguishing coloring partitions of the path P_n on n vertices with at most k parts.
Note that, for any graph G, Psi_k(G) = Sum_{i<=k} psi_i(G), where psi_i(G) is the number of non-equivalent distinguishing coloring partitions of G with exactly i parts. For instance, here we have T(n,k) = Sum_{i<=k} A309748(n,i).
LINKS
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
Mohammad Hadi Shekarriz, GAP code
FORMULA
T(n, k) = Sum_{i=1..k} A309748(n,i).
EXAMPLE
Table begins:
======================================================================
n\k| 1 2 3 4 5 6 7 8 9 10
---+------------------------------------------------------------------
1 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ...
2 | 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 ...
3 | 0, 1, 2, 2, 2, 2, 2, 2, 2, 2 ...
4 | 0, 4, 8, 9, 9, 9, 9, 9, 9, 9 ...
5 | 0, 6, 20, 26, 27, 27, 27, 27, 27, 27 ...
6 | 0, 16, 65, 102, 111, 112, 112, 112, 112, 112 ...
7 | 0, 28, 182, 364, 440, 452, 453, 453, 453, 453 ...
8 | 0, 64, 560, 1436, 1978, 2120, 2136, 2137, 2137, 2137 ...
9 | 0, 120, 1640, 5560, 9082, 10428, 10670, 10690, 10691, 10691 ...
10 | 0, 256, 4961, 22136, 43528, 55039, 58019, 58409, 58434, 58435 ...
...
For n=4, we can partition the vertices of P_4 into at most 3 parts in 8 ways such that all these partitions induce distinguishing colorings for P_4 and that all the 8 partitions are non-equivalent. The partitions are as follows:
{ { 1 }, { 2 }, { 3, 4 } }
{ { 1 }, { 2, 3 }, { 4 } }
{ { 1 }, { 2, 4 }, { 3 } }
{ { 1, 4 }, { 2 }, { 3 } }
{ { 1 }, { 2, 3, 4 } }
{ { 1, 2 }, { 3, 4 } }
{ { 1, 2, 4 }, { 3 } }
{ { 1, 3 }, { 2, 4 } }
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Mohammad Hadi Shekarriz, Aug 13 2019
STATUS
approved