How do I go about checking if the graph with the given paramaters is a Cayley graph?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ What is the structure of the subgraph induced by the neighbourhood of a vertex? $\endgroup$– Andrew D. KingCommented Jun 1, 2012 at 17:56
-
$\begingroup$ Related quetsion: mathoverflow.net/questions/14830/which-graphs-are-cayley-graphs/… $\endgroup$– Spice the BirdCommented Jun 1, 2012 at 18:44
-
4$\begingroup$ 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. $\endgroup$– Brendan McKayCommented Jun 3, 2012 at 14:10
-
1$\begingroup$ The Wikipedia article on the Hoffman-Singleton graph has "Cayley graph" listed among its properties. So that must be wrong! $\endgroup$– Derek HoltCommented Jun 3, 2012 at 16:05
-
3$\begingroup$ I checked again by finding generators and confirming they are all even permutations. I'll fix Wikipedia, thanks for noticing. $\endgroup$– Brendan McKayCommented Jun 5, 2012 at 2:02
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
4
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.
answered Jun 2, 2012 at 5:52
-
$\begingroup$ 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. $\endgroup$– verretCommented Jun 3, 2012 at 7:30
-
$\begingroup$ 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. $\endgroup$ Commented Jun 7, 2012 at 19:53
-
$\begingroup$ +1 for the word "integrality-challenged" which I've never seen before and sounds quite cool :) $\endgroup$ Commented Jun 8, 2012 at 7:16
-
$\begingroup$ 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? $\endgroup$– verretCommented Jun 8, 2012 at 8:39