cp's OEIS Frontend

A320583 Irregular triangle read by rows: T(n,k) is the number of connected permutation graphs on n vertices with domination number k, with 1 <= k <= floor(n/2).

%I A320583 #18 Oct 18 2018 08:59:21
%S A320583 1,1,3,10,3,43,28,223,236,2,1364,1842,62,9643,18433,1015,2,77545,
%T A320583 181568,14146,84,699954,1938199,189077,2093,2
%N A320583 Irregular triangle read by rows: T(n,k) is the number of connected permutation graphs on n vertices with domination number k, with 1 <= k <= floor(n/2).
%H A320583 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 A320583 T(n,n/2) = 2 for even n. See Theorem 4.5 in the link by Theresa Baren, et al.
%F A320583 T(n,k) = A320578(n,k) - A320579(n,k).
%F A320583 T(n,1) = A320578(n,1).
%e A320583 Triangle begins:
%e A320583     1;
%e A320583     1;
%e A320583     3;
%e A320583    10,   3;
%e A320583    43,  28;
%e A320583   223, 236,  2;
%e A320583   ...
%o A320583 (Python)
%o A320583 import networkx as nx
%o A320583 import math
%o A320583 def permutation(lst):
%o A320583     if len(lst) == 0:
%o A320583         return []
%o A320583     if len(lst) == 1:
%o A320583         return [lst]
%o A320583     l = []
%o A320583     for i in range(len(lst)):
%o A320583         m = lst[i]
%o A320583         remLst = lst[:i] + lst[i + 1:]
%o A320583         for p in permutation(remLst):
%o A320583             l.append([m] + p)
%o A320583     return l
%o A320583 def generatePermsOfSizeN(n):
%o A320583     lst = []
%o A320583     for i in range(n):
%o A320583         lst.append(i+1)
%o A320583     return permutation(lst)
%o A320583 def powersetHelper(A):
%o A320583     if A == []:
%o A320583         return [[]]
%o A320583     a = A[0]
%o A320583     incomplete_pset = powersetHelper(A[1:])
%o A320583     rest = []
%o A320583     for set in incomplete_pset:
%o A320583         rest.append([a] + set)
%o A320583     return rest + incomplete_pset
%o A320583 def powerset(A):
%o A320583     ps = powersetHelper(A)
%o A320583     ps.sort(key = len)
%o A320583     return ps
%o A320583     print(ps)
%o A320583 def countcnctdDomNumbersOnN(n):
%o A320583     lst=[]
%o A320583     l=[]
%o A320583     perms = generatePermsOfSizeN(n)
%o A320583     for i in range(n):
%o A320583         lst.append(i+1)
%o A320583     ps = powerset(lst)
%o A320583     dic={}
%o A320583     for perm in perms:
%o A320583         tempGraph = nx.Graph()
%o A320583         tempGraph.add_nodes_from(perm)
%o A320583         for i in range(len(perm)):
%o A320583             for k in range(i+1, len(perm)):
%o A320583                 if perm[k] < perm[i]:
%o A320583                     tempGraph.add_edge(perm[i], perm[k])
%o A320583         if nx.is_connected(tempGraph)==True:
%o A320583             for p in ps:
%o A320583                 if nx.is_dominating_set(tempGraph,p):
%o A320583                     dom = len(p)
%o A320583                     if dom in dic:
%o A320583                         dic[dom] += 1
%o A320583                         break
%o A320583                     else:
%o A320583                         dic[dom] = 1
%o A320583                         break
%o A320583     return dic
%Y A320583 Cf. A320578, A320579.
%K A320583 nonn,hard,tabf,more
%O A320583 1,3
%A A320583 _James Hammer_, _Daniel A. McGinnis_, Oct 15 2018