7
$\begingroup$

Sometimes specific graphs have very nice properties and tend to pop up often enough that they have been given names like the Petersen Graph, the Rook's Graph, the Durer Graph, etc. Is there any convenient way to "look up" a graph without first knowing its name in order to find out if it has a name? It would be nice if there were something less tedious than looking over lists of named graphs (which seemed to be the only option mentioned in this question), or trying to determine properties of a graph and then Googling those properties.

WolframAlpha seems like the most likely candidate, but it times out when I enter the edgelist. And it seems kinda inefficient to make a "What's this Graph" post on MathSE whenever this comes up.


If anyone wants the specific challenge, the current graph in question is the following $6$-regular graph with $10$ vertices and $30$ edges. This graph ($G$) has the property that for any two vertices $v_1$,$v_2$ the graphs $G-v_1$ and $G-v_2$ are isomorphic. Similarly $G-e_1$ and $G-e_2$ are isomorphic for any two edges. I'm pretty sure this implies that the graph is symmetric. $$ \left\{(1,3),(1,4),(1,6),(1,7),(1,9),(1,10),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,5),(3,6),(3,8),(3,9),(3,10),(4,6),(4,7),(4,8),(4,10),(5,7),(5,8),(5,9),(5,10),(6,8),(6,9),(7,9),(7,10),(8,10)\right\} $$ Mathematica Rending of the Graph

Work done on this page shows that there are $21$ $6$-regular graphs on $10$ vertices, so my graph may not be as special as I thought and may not have a name.

$\endgroup$
  • $\begingroup$ The answers to this similar question might be helpful. $\endgroup$ – joriki Sep 10 '15 at 14:33
  • 1
    $\begingroup$ @joriki, yeah, I did see that post (I linked to it in my question). Most of the responses in that question link to some list of graphs to look over, and not really a searchable list of graphs. The House of Graphs is pretty close to what I am looking for, but it just narrows down the list of graphs you have to manually check whether or not they match your graph. It doesn't quite offer the convenience that, say, OEIS does for integer sequences. $\endgroup$ – Mike Pierce Sep 10 '15 at 15:40
  • 1
    $\begingroup$ @MikePierce you can search for a specific graph on HoG by generating its graph6 string and then searching by that -- there's an option to upload a g6 file at the bottom of hog.grinvin.org/SearchGraph.action $\endgroup$ – Gregory J. Puleo Sep 12 '15 at 17:07
2
$\begingroup$

It's the 5-triangular graph. Also called the (5,2)-Johnson graph. I used Mathematica, which has an index of graphs, and found the 10-vertex, 30-edge symmetric graphs. Then I calculated the spectrum / characteristic polynomial of your graph to verify the match.

Oh -- and complement of the Petersen graph. I should have started by taking the complement anyways, but I'd already found it by that point. If if twice the valency exceeds the vertex count, look at the graph complement first.


To provide a few snippets of code, the function GraphData[] is used to access the index of graphs available in Mathematica. To select the names of all symmetric graphs with $10$ vertices and $30$ edges in the index, you could use the following code that returns just the $5$-triangular graph:

Select[GraphData["Symmetric", 10], GraphData[#, "EdgeCount"] == 30 &]

To more directly answer the question, if you just have the edgelist of a graph and want to search the index (and don't want to bother calculating any properties of that graph), you could use this:

g = Graph[(* EDGELIST *)];
Select[GraphData[], IsomorphicGraphQ[GraphData[#], g] &]

This last line is admittedly slow, but can can be sped up considerably by adding a few conditions into the first GraphData[].

$\endgroup$
  • $\begingroup$ Thank you! I've been working with graphs in Mathematica for quite some time now, and it's amazing that I've never heard of its graph index before. Do you mind if I edit you answer to provide a few code snippets? $\endgroup$ – Mike Pierce Sep 12 '15 at 16:43
  • $\begingroup$ Start with GraphData[10] $\endgroup$ – Ed Pegg Sep 12 '15 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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