OFFSET
1,4
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.
EXAMPLE
Triangle begins:
1;
1, 1;
3, 2, 1;
10, 10, 3, 1;
43, 54, 18, 4, 1;
223, 351, 113, 27, 5, 1;
...
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
James Hammer, Daniel A. McGinnis, Oct 15 2018
STATUS
approved