Welcome to MathOverflow

Question

2

How do I go about checking if the graph with the given paramaters is a Cayley graph?

edited Jun 1 at 20:16

François G. Dorais♦
22.6k●2●48●113

asked Jun 1 at 17:17

Benedicto
23●2

What is the structure of the subgraph induced by the neighbourhood of a vertex? – Andrew D. King Jun 1 at 17:56

Related quetsion: mathoverflow.net/questions/14830/… – Spice the Bird Jun 1 at 18:44

The subgraph induced by a vertex is a graph with 8 vertices and 12 edges which can be drawn as follows: Start with two graphs, 5 vertices on a pentagon and a ray with 3 vertices. We take the subgraph to be unduced by the middle vertex on the ray. The middle vertex on the the ray is adjacent to all the vertices on the graph. – Benedicto Jun 1 at 18:47

The puzzling thing about this question is that there is a well-known regular graph with 50 vertices and degree 7 (the Moore graph) with automorphism group of order 252000 and structure $P \Sigma U(3,5)$. That graph has no triangles and the point stabilizer acts as $S_7$ on the vertices adjoining a fixed vertex. But that is clearly not the graph you are talking about! To help me identify your graph, do you know anything about the structure of its automorphism group of order 288000? – Derek Holt Jun 3 at 10:15

2

Yes, also known as the Hoffman-Singleton graph. The easiest way I know of showing that it is not a Cayley graph is to note that its automorphism group lies in $A_{50}$, but a 2-element in a regular subgroup would be odd. – Brendan McKay Jun 3 at 14:10

show 2 more comments

verret · Accepted Answer · 2012-06-01 19:02:37Z UTC

A graph is Cayley if and only if its automorphism group has a regular subgroup. A computer algebra system such as Magma or GAP (I think) usually can determine if a permutation group of order 288000 has a regular subgroup rather quickly.

If you can give the graph or the automorphism group in some common format, somebody might even run the computation for you.

Brendan McKay · Answer 2 · 2012-06-03 07:42:02Z UTC

There isn't any good general computational method for determining whether a permutation group has a regular subgroup. It was recently described to me by an authority on permutation group algorithms as an important unsolved problem. However, degree 50 is quite small and, as verret noted, various ad hoc methods available in algebra packages are sure to be successful.

However, the information you have provided is impossible for a vertex-transitive graph regardless of whether or not it is a Cayley graph. Suppose it is vertex-transitive. Since 288000 is divisible by 3, there is an automorphism $g$ of order 3. The order 50 is not divisible by 3. Therefore there is a vertex $v$ fixed by $g$ that is adjacent to a vertex moved by $g$. (I didn't assume the graph is connected here.) This means that the 7-vertex neighbourhood graph of $v$ has an automorphism of order 3, but the neighbourhood you told us in your comment (a pentagon and two isolated vertices) does not have such an automorphism.

Therefore your graph is not a Cayley graph. Unless you got the group order wrong? The largest plausible group order for a connected transitive graph with that neighbourhood graph is 1000.

EDIT: Verret's comment to this answer suggested a simpler argument. If there are 5 triangles on each vertex and it has 50 vertices, the total number of triangles must be $\frac{50\times 5}{3}$ which is integrality-challenged.

Regular graph of order 50, degree 7 and Automorphism group of order 288000. How to check if it is Cayley

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.