8
$\begingroup$

I know my way around Mathematica pretty well, however I have not been able to find any built-in functionality for testing a (graph-theoretic) graph for being

  • symmetric (arc transitive) – this is the one I need the most
  • distance transitive
  • distance regular
  • strongly regular
  • edge transitive
  • vertex transitive

(SymmetricQ does not test whether or not a graph is symmetric/arc transitive; it "tests if the edges of a given graph represent a symmetric relation".)

(For testing regularity, Mathematica had the function RegularQ, but it became defunct by version 10. It doesn't matter though, regularity is easily tested using the function VertexDegree.)

Where are these functions? Am I not seeing them somewhere? I would find it very disappointing if Mathematica does not have built-in functions for determining these fundamental properties of graphs. If Mathematica doesn't, does anyone know why?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Have you seen this? $\endgroup$
    – Sektor
    May 30, 2018 at 19:28
  • $\begingroup$ No, I did not. Thank you. That seems to have tests for vertex transitivity and edge transitivity, but I don't see tests for the others. It has the function IGSymmetricQ, but that seems to test for graphs that are both vertex-transitive and edge-transitive, not graphs that are arc-transitive (unfortunately, the word "symmetric" has two different definitions - see en.wikipedia.org/wiki/Symmetric_graph). $\endgroup$
    – Just Some Old Man
    May 30, 2018 at 19:59
  • 4
    $\begingroup$ If you first turn your undirected graph into a directed graph, with edges going in both directions wherever the original graph had an edge, then IGSymmetricQ will use your definition. $\endgroup$
    – Misha Lavrov
    May 30, 2018 at 20:52
  • $\begingroup$ Thank you Sektor and Misha. I will learn this. Graph Theory is outside my primary field but it came up in some research. If either of you want to post your comments as answers I will gladly accept and upvote. Does anyone know about functions that exist for testing the others (strongly regular or distance regular), or would I have to make my own functions? $\endgroup$
    – Just Some Old Man
    May 30, 2018 at 21:21

2 Answers 2

Reset to default
9
$\begingroup$

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:

  1. EdgeList[g][[1]] gives us some edge of the graph g. It appears as something like 1<->2, so it is ordered; it might as well be the list {1,2}.
  2. Then PermutationReplace gives us the orbit of this ordered pair under the action of the group.
  3. Join[EdgeList[g], Reverse /@ EdgeList[g]] lists all edges of the graph (in both possible orders).
  4. 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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ You can read the source code of IGraph/M. IGVertexTransitiveQ is a feature unique to IGraph/M, not the igraph core library. It is implemented as With[{elems = Range@VertexCount[graph]}, GroupOrbits[PermutationGroup@IGBlissAutomorphismGroup[graph], elems] === {elems} ]. PermutationGroup@IGBlissAutomorphismGroup[...] basically does the same as GraphAutomorphismGroup. It uses the Bliss library through igraph. Bliss is much faster than nauty, which Mathematica uses. However, there is a constant overhead in converting the graph to the appropriate format. $\endgroup$
    – Szabolcs
    May 31, 2018 at 22:10
  • $\begingroup$ This built-in functions tend to be faster for small graph, but Bliss will usually be (much) faster for large and difficult graphs. $\endgroup$
    – Szabolcs
    May 31, 2018 at 22:10
  • 1
    $\begingroup$ The DirectedGraph function is easier to use for creating bidirectional directed edges. $\endgroup$
    – Szabolcs
    May 31, 2018 at 22:14
  • 1
    $\begingroup$ The latest release of IGraph/M implements all the properties the OP was asking for. Now it uses C implementations which is likely to be as fast or faster than what you might find in any other package. Any feedback is welcome. $\endgroup$
    – Szabolcs
    May 5, 2019 at 11:05
8
$\begingroup$

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 using DirectedGraph 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:

enter image description here

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
]
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.