A320578 Triangle read by rows: T(n,k) is the number of permutation graphs on n vertices with domination number k, with 1 <= k <= n.
1, 1, 1, 3, 2, 1, 10, 10, 3, 1, 43, 54, 18, 4, 1, 223, 351, 113, 27, 5, 1, 1364, 2613, 833, 186, 37, 6, 1, 9643, 21965, 6921, 1461, 274, 48, 7, 1, 77545, 205780, 64128, 12727, 2253, 378, 60, 8, 1, 699954, 2127068, 655391, 122345, 20230, 3230, 499, 73, 9, 1
Offset: 1
Examples
Triangle begins:
1;
1, 1;
3, 2, 1;
10, 10, 3, 1;
43, 54, 18, 4, 1;
223, 351, 113, 27, 5, 1;
...
Links
- Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points, arXiv:1810.03409 [math.CO], 2018.
Programs
-
Python
import networkx as nx import math def permutation(lst): if len(lst) == 0: return [] if len(lst) == 1: return [lst] l = [] for i in range(len(lst)): m = lst[i] remLst = lst[:i] + lst[i + 1:] for p in permutation(remLst): l.append([m] + p) return l def generatePermsOfSizeN(n): lst = [] for i in range(n): lst.append(i+1) return permutation(lst) def powersetHelper(A): if A == []: return [[]] a = A[0] incomplete_pset = powersetHelper(A[1:]) rest = [] for set in incomplete_pset: rest.append([a] + set) return rest + incomplete_pset def powerset(A): ps = powersetHelper(A) ps.sort(key = len) return ps print(ps) def countDomNumbersOnN(n): lst=[] perms = generatePermsOfSizeN(n) for i in range(n): lst.append(i+1) ps = powerset(lst) dic={} for perm in perms: tempGraph = nx.Graph() tempGraph.add_nodes_from(perm) for i in range(len(perm)): for k in range(i+1, len(perm)): if perm[k] < perm[i]: tempGraph.add_edge(perm[i], perm[k]) for p in ps: if nx.is_dominating_set(tempGraph,p): dom = len(p) if dom in dic: dic[dom] += 1 break else: dic[dom] = 1 break return dic