# Revision history [back]

Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:

• to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not
• for each notrivial automorphism of the group g, you add the constraint that the sum of the variables corresponding to the non-fixed points by g is at least 1 (which means that at least one non-fixed vertex belongs to the set you are looking for). (here i find the non-fixed points of g by looking to its cycle representation)
• then you ask a MILP solver to minimize the sum of all variables (which means that you want the set to be as small as possible)

Here is th code:

def determining_set(G):
p = MixedIntegerLinearProgram(maximization=False)
x = p.new_variable(binary=True)
for g in G.automorphism_group():
if not g.is_one():
p.add_constraint(sum(x[i] for i in flatten(g.cycle_tuples())) >= 1)
p.solve()
sol = p.get_values(x)
return [i for i in sol if sol[i]]


Which you can test:

sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]

sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]


Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:

• to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not
• for each notrivial automorphism of the group g, you add the constraint that the sum of the variables corresponding to the non-fixed points by g is at least 1 (which means that at least one non-fixed vertex belongs to the set you are looking for). (here i find the non-fixed points of g by looking to its cycle representation)
• then you ask a MILP solver to minimize the sum of all variables (which means that you want the set to be as small as possible)

Here is th code:

def determining_set(G):
p = MixedIntegerLinearProgram(maximization=False)
x = p.new_variable(binary=True)
for g in G.automorphism_group():
if not g.is_one():
p.add_constraint(sum(x[i] for i in flatten(g.cycle_tuples())) >= 1)
p.solve()
sol = p.get_values(x)
return [i for i in sol if sol[i]]
sol[i] != 0]


Which you can test:

sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]

sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]