Testing for Symmetry and Regularity in (Graph-Theoretic) Graphs
In general, if we first use GraphAutomorphismGroup
to find the automorphism group of a graph, it is not hard to figure out if it acts transitively on vertices, edges, arcs, pairs of vertices at distance $k$, or any other objects.
For example, to test if a graph g
is arc-transitive: test if
Complement[Join[EdgeList[g], Reverse /@ EdgeList[g]],
PermutationReplace[
EdgeList[g][[1]],
GraphAutomorphismGroup[g]]] == {}
To unpack this:
EdgeList[g][[1]]
gives us some edge of the graphg
. It appears as something like1<->2
, so it is ordered; it might as well be the list{1,2}
.- Then
PermutationReplace
gives us the orbit of this ordered pair under the action of the group. Join[EdgeList[g], Reverse /@ EdgeList[g]]
lists all edges of the graph (in both possible orders).Complement[..., ...] == {}
checks that everything is in the orbit of the edge we picked.
To generalize this, simply replace steps 1 and 3. For step 1, generate a single object of the type you want; for step 3, generate a list of all the objects.
(A tricky detail: when testing for edge-transitive graphs, we should do Sort /@ PermutationReplace[...]
in step 2, so that we generate every edge in the orbit in its canonical representation.)
This approach covers all the transitivity properties. To test for distance regular and strongly regular graphs, begin with GraphDistanceMatrix
, and the rest is no longer a graph theory problem.
We can also use IGraph/M, as pointed out in the comments on the question, which tests if a graph is vertex transitive (IGVertexTransitiveQ
), edge transitive (IGEdgeTransitiveQ
) and both (IGSymmetricQ
).
If we test the directed version of a graph for being symmetric, by using
IGSymmetricQ[DirectedGraph[g]]
rather than simply IGSymmetricGraphQ[g]
, it will test for arc transitivity, which is just asking if every directed edge can be mapped to every other directed edge.
For large graphs, the igraph approach will be faster than the pure Mathematica code, as pointed out in the comments on this answer.
IGraph/M 0.3.111 now has fast functions to test for all of these. Please look under Isomorphism -> Properties related to the automorphism group in the documentation.
Regular:
IGRegularQ
Vertex transitive:
IGVertexTransitiveQ
.Edge transitive:
IGEdgeTransitiveQ
.Strongly regular:
IGStronglyRegularQ
.Distance regular:
IGDistanceRegularQ
.Distance transitive:
IGDistanceTransitiveQ
.Arc transitive:
IGEdgeTransitiveQ@DirectedGraph[#]&
. Note that the term symmetric is used in different ways by different authors.IGSymmetricQ
checks if a graph is both vertex and edge transitive. To check for arc transitivity in an undirected graph, first convert it to a directed one usingDirectedGraph
then check for edge transitivity.
These are implemented in C++ and are likely to be as fast as any alternatives you might find in any other software package.
Here's a table of a few graphs which all have different properties:
Needs["IGraphM`"]
graphs = {StarGraph[4], IGSquareLattice[{2, 3}, "Periodic" -> True],
HypercubeGraph[3], GraphData[{"Rook", {4, 4}}],
GraphData["ShrikhandeGraph"], GraphData["HoltGraph"],
GraphData["Tutte12Cage"], GraphData[{"Paulus", {25, 1}}]};
functions = <|"regular" -> IGRegularQ,
"strongly regular" -> IGStronglyRegularQ,
"distance regular" -> IGDistanceRegularQ,
"vertex transitive" -> IGVertexTransitiveQ,
"edge transitive" -> IGEdgeTransitiveQ,
"arc transitive" -> IGEdgeTransitiveQ@*DirectedGraph,
"distance transitive" -> IGDistanceTransitiveQ|>;
TableForm[
Through[Values[functions][#]] & /@ graphs,
TableHeadings -> {Show[#, ImageSize -> 60] & /@ graphs, Keys[functions]},
TableDirections -> Row
]