Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

How can I compute the minimal determining set (fixing set) of a graph?

Definition of determining set (or fixing set): A set S ⊆ V (G) is a determining set if and only if the stabilizing set Stab(S) of S, defined as Stab(S) := {g ∈ Aut(G) | g(v) = v, for all v ∈ S} only contains the trivial automorphism.

The above definition simply means that at least one of the vertices in the determining set S must not be fixed by each automorphism, or more simply, each automorphism must contain one of the nodes in the S.

Now, the question is, having the automorphism group of graph G, how we can compute the smallest set of nodes (or a minimal set of nodes) that have the property of being a determining set for the graph G?

(If someone don't want to be confused with above math, never mind it. Just read the below lines where I have explained the question in another form with no complexity.)

In other words, the question is, having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automporphism in Aut(G) contains at least one of the nodes in a set S?

For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary.

How can I compute the minimal determining set (fixing set) of a graph?

Definition of determining set (or fixing set): A set S ⊆ V (G) is a determining set if and only if the stabilizing set Stab(S) of S, defined as Stab(S) := {g ∈ Aut(G) | g(v) = v, for all v ∈ S} only contains the trivial automorphism.

The above definition simply means that at least one of the vertices in the determining set S must not be fixed by each automorphism, or more simply, each automorphism must contain one of the nodes in the S.

Now, the question is, having the automorphism group of graph G, how we can compute the smallest set of nodes (or a minimal set of nodes) that have the property of being a determining set for the graph G?

(If someone don't want to be confused with above math, never mind it. Just read the below lines where I have explained the question in another form with no complexity.)

In other words, the question is, having Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automporphism in Aut(G) contains at least one of the nodes in a set S?

For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary. necessary.

How can I compute the minimal determining set (fixing set) of a graph?

Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automporphism in Aut(G) contains at least one of the nodes in a set S?

For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary.

How can I compute the minimal determining set (fixing set) of a graph?

Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automporphism in Aut(G) contains at least one of the nodes in a set S?

For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary.