Calculator form
Use edge lists or adjacency matrices. Exact search is limited to 9 vertices for dependable browser-friendly performance.
Example data table
| Example graph | Vertices | Edges | Automorphism count | Why it matters |
|---|---|---|---|---|
| Cycle C4 | 4 | 4 | 8 | Captures rotational and reflection symmetry. |
| Path P5 | 5 | 4 | 2 | Only reversal preserves adjacency. |
| Complete K4 | 4 | 6 | 24 | Every vertex permutation is valid. |
| Star K1,4 | 5 | 4 | 24 | Leaf permutations keep the hub fixed. |
Formula used
Automorphism condition: A permutation p is valid when A[i, j] = A[p(i), p(j)] for every vertex pair.
Group order: |Aut(G)| equals the number of valid permutations that preserve adjacency, direction, loop status, and chosen vertex colors.
Orbit of a vertex: Orbit(v) = {p(v) : p ∈ Aut(G)}. Vertices in the same orbit are structurally interchangeable.
Symmetry ratio: Symmetry ratio = |Aut(G)| / n! . This compares observed symmetry against all possible vertex permutations.
How to use this calculator
- Enter a graph name and the total number of vertices.
- Choose whether the graph is directed or undirected.
- Select edge list or adjacency matrix input mode.
- Provide optional vertex colors when symmetry must preserve labels or partitions.
- Paste the graph data into the main input area.
- Enable self-loops only when your graph definition includes them.
- Press the calculate button to get exact automorphism counts, orbit groups, and fixed-point statistics.
- Use the export buttons to save a CSV summary or a PDF report.
FAQs
1) What does an automorphism mean?
It is a vertex relabeling that leaves the graph unchanged. Every edge, direction, loop, and chosen color constraint must still match after the permutation.
2) Why are orbit groups useful?
Orbit groups show which vertices are interchangeable under graph symmetries. They help identify repeated roles, equivalent nodes, and structurally identical positions.
3) Why is the exact solver limited to 9 vertices?
Automorphism search grows extremely fast because it explores permutations. A 9-vertex cap keeps the page accurate, responsive, and practical for direct browser use.
4) Do vertex colors affect the answer?
Yes. Colors restrict allowed permutations. Vertices can only map onto vertices with the same color, which often reduces automorphism count and changes orbit partitions.
5) Can I use directed graphs?
Yes. The calculator checks both incoming and outgoing adjacency. A direction-preserving symmetry must keep arrow orientation intact for every mapped edge.
6) What is the symmetry ratio?
It compares the observed automorphism count with all possible vertex permutations. Higher values indicate stronger structural symmetry relative to graph size.
7) Why might a graph have only one automorphism?
That means only the identity permutation works. The graph is asymmetric, so no nontrivial vertex relabeling preserves its full structure.
8) What does the Plotly graph show?
It shows the submitted network with vertices placed on a circle. Colors indicate orbit membership, while larger markers highlight vertices in larger orbits.