A320579 Triangle read by rows: T(n,k) is the number of disconnected permutation graphs on n vertices with domination number k, with 2 <= k <= n.
1, 2, 1, 7, 3, 1, 26, 18, 4, 1, 115, 111, 27, 5, 1, 592, 771, 186, 37, 6, 1, 3532, 5906, 1459, 274, 48, 7, 1, 24212, 49982, 12643, 2253, 378, 60, 8, 1, 188869, 466314, 120252, 20228, 3230, 499, 73, 9, 1
Offset: 2
Examples
Triangle begins:
1;
2, 1;
7, 3, 1;
26, 18, 4, 1;
115, 111, 27, 5, 1;
592, 771, 186, 37, 6, 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 countdisDomNumbersOnN(n): lst=[] l=[] 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]) if nx.is_connected(tempGraph)==False: 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