login
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.
2
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,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.
FORMULA
T(n,k) = A320579(n,k) + A320583(n,k).
T(n,1) = A320583(n,1).
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
nonn,hard,tabl
AUTHOR
STATUS
approved