cp's OEIS Frontend

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.

%I A320579 #21 Oct 18 2018 09:46:29
%S A320579 1,2,1,7,3,1,26,18,4,1,115,111,27,5,1,592,771,186,37,6,1,3532,5906,
%T A320579 1459,274,48,7,1,24212,49982,12643,2253,378,60,8,1,188869,466314,
%U A320579 120252,20228,3230,499,73,9,1
%N 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.
%H A320579 Theresa Baren, Michael Cory, Mia Friedberg, Peter Gardner, James Hammer, Joshua Harrington, Daniel McGinnis, Riley Waechter, Tony W. H. Wong, <a href="https://arxiv.org/abs/1810.03409">On the Domination Number of Permutation Graphs and an Application to Strong Fixed Points</a>, arXiv:1810.03409 [math.CO], 2018.
%F A320579 T(n,k) = A320578(n,k) - A320583(n,k).
%e A320579 Triangle begins:
%e A320579     1;
%e A320579     2,   1;
%e A320579     7,   3,   1;
%e A320579    26,  18,   4,  1;
%e A320579   115, 111,  27,  5,  1;
%e A320579   592, 771, 186, 37,  6,  1;
%e A320579   ...
%o A320579 (Python)
%o A320579 import networkx as nx
%o A320579 import math
%o A320579 def permutation(lst):
%o A320579     if len(lst) == 0:
%o A320579         return []
%o A320579     if len(lst) == 1:
%o A320579         return [lst]
%o A320579     l = []
%o A320579     for i in range(len(lst)):
%o A320579         m = lst[i]
%o A320579         remLst = lst[:i] + lst[i + 1:]
%o A320579         for p in permutation(remLst):
%o A320579             l.append([m] + p)
%o A320579     return l
%o A320579 def generatePermsOfSizeN(n):
%o A320579     lst = []
%o A320579     for i in range(n):
%o A320579         lst.append(i+1)
%o A320579     return permutation(lst)
%o A320579 def powersetHelper(A):
%o A320579     if A == []:
%o A320579         return [[]]
%o A320579     a = A[0]
%o A320579     incomplete_pset = powersetHelper(A[1:])
%o A320579     rest = []
%o A320579     for set in incomplete_pset:
%o A320579         rest.append([a] + set)
%o A320579     return rest + incomplete_pset
%o A320579 def powerset(A):
%o A320579     ps = powersetHelper(A)
%o A320579     ps.sort(key = len)
%o A320579     return ps
%o A320579     print(ps)
%o A320579 def countdisDomNumbersOnN(n):
%o A320579     lst=[]
%o A320579     l=[]
%o A320579     perms = generatePermsOfSizeN(n)
%o A320579     for i in range(n):
%o A320579         lst.append(i+1)
%o A320579     ps = powerset(lst)
%o A320579     dic={}
%o A320579     for perm in perms:
%o A320579         tempGraph = nx.Graph()
%o A320579         tempGraph.add_nodes_from(perm)
%o A320579         for i in range(len(perm)):
%o A320579             for k in range(i+1, len(perm)):
%o A320579                 if perm[k] < perm[i]:
%o A320579                     tempGraph.add_edge(perm[i], perm[k])
%o A320579         if nx.is_connected(tempGraph)==False:
%o A320579             for p in ps:
%o A320579                 if nx.is_dominating_set(tempGraph,p):
%o A320579                     dom = len(p)
%o A320579                     if dom in dic:
%o A320579                         dic[dom] += 1
%o A320579                         break
%o A320579                     else:
%o A320579                         dic[dom] = 1
%o A320579                         break
%o A320579     return dic
%Y A320579 CF. A320578, A320583.
%K A320579 nonn,tabl,hard,more
%O A320579 2,2
%A A320579 _James Hammer_, _Daniel A. McGinnis_, Oct 15 2018