We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 June 2016
The class of Cayley digraphs far from exhausts all vertex-transitive digraphs. The same holds even for the undirected case: The smallest example of a non- Cayley vertex-transitive graph is the Petersen graph; we have already seen that this is not a Cayley graph.
In an earlier chapter we discussed the problem of obtaining non-Cayley vertex-transitive graphs, and we have shown one simple, systematic way of obtaining them. Such constructions often lead to very interesting classes of graphs. The size of the automorphism group is generally not a good indicator for deciding whether a vertex-transitive graph is Cayley, in the sense that a graph may be rich with automorphisms and be non-Cayley, or have a small automorphism group and be Cayley. Examples for the former situation are provided by the odd graphs. The latter case arises with GRRs: in this case, we have a paradox because the smallest possible size for Aut (G) guarantees that the graph is Cayley.
The five classes of graphs that we are going to introduce in this chapter (the generalised Petersen graphs, Kneser graphs, metacirculant graphs, quasi- Cayley digraphs and generalised Cayley graphs) are essentially different. Each of these classes contains infinitely many further non-Cayley graphs and digraphs and some are not even vertex-transitive.
While the methods of orbital graphs and double-cosets representations, as described in the previous chapters, enable us to represent all possible vertextransitive graphs, a general classification theorem for them is presently far beyond us.
Special cases of vertex-transitive graphs have been classified. It is known that all those of prime order are Cayley (actually, circulant graphs, that is, Cayley graphs of a cyclic group). A classification result has also been obtained for the next case, that of order equal to the product of two primes. This required the help of the classification theorem for finite simple groups and further deep group-theoretical results. Further details are given in Section 7.3.
In view of these remarks, this chapter is not intended to offer classification theorems, but rather to illustrate several significant classes of graphs having a good symmetry (mostly, vertex-transitivity).
Each of the next sections is devoted to one of these classes, collecting results that are mostly available only in journal articles.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
