Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
What is the structure of the subgraph induced by the neighbourhood of a vertex? –  Andrew D. King Jun 1 '12 at 17:56
    
    
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 '12 at 18:47
3  
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 '12 at 14:10
1  
I checked again by finding generators and confirming they are all even permutations. I'll fix Wikipedia, thanks for noticing. –  Brendan McKay Jun 5 '12 at 2:02

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Good point. Now that I think about it, even without the order of the automorphism group, the rest of the data seems incompatible with vertex-transitivity. Consider the graph induced by edges which are in a triangle. This graph would be vertex-transitive, 5-valent and have a 5-cycle as "local graph". I think this forces it to be a union of icosahedrons and hence the number of vertices should be a multiple of 12. –  verret Jun 3 '12 at 7:30
    
Thanks everyone for the responses. About Brendan's explanation, I would like to know if there is a formal theorem or result I can QUOTE to the effect that in such a case, where one can exhibit a $g \in \mbox{Aut}~\Gamma$ that is not in the induced neighborhood of a vertex, then the graph is not Cayley. –  Benedicto Jun 7 '12 at 19:53
    
+1 for the word "integrality-challenged" which I've never seen before and sounds quite cool :) –  Tom De Medts Jun 8 '12 at 7:16
    
Benedicto, both of Brendan's arguments show that the graph is not even vertex-transitive. The second one (counting triangles) is much simpler and would not require any reference (the first one depends on a somewhat folklore lemma that is commonly used in this area but hard to find proved anywhere). Note that it actually shows that a graph of that order and degree cannot have the local graph you described at every vertex and hence cannot be vertex-transitive. Are you sure you gave the correct local graph? –  verret Jun 8 '12 at 8:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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