Graph Symmetry: Algebraic Methods and Applications
The last decade has seen parallel developments in computer science and combinatorics, both dealing with networks having strong symmetry properties. Both developments are centred on Cayley graphs: in the design of large interconnection networks, Cayley graphs arise as one of the most frequently used models; on the mathematical side, they play a central role as the prototypes of vertex-transitive graphs. The surveys published here provide an account of these developments, with a strong emphasis on the fruitful interplay of methods from group theory and graph theory that characterises the subject. Topics covered include: combinatorial properties of various hierarchical families of Cayley graphs (fault tolerance, diameter, routing, forwarding indices, etc.); Laplace eigenvalues of graphs and their relations to forwarding problems, isoperimetric properties, partition problems, and random walks on graphs; vertex-transitive graphs of small orders and of orders having few prime factors; distance transitive graphs; isomorphism problems for Cayley graphs of cyclic groups; infinite vertex-transitive graphs (the random graph and generalisations, actions of the automorphisms on ray ends, relations to the growth rate of the graph).
What people are saying - Write a review
We haven't found any reviews in the usual places.
Isomorphism and Cayley graphs on abelian groups
Oligomorphic groups and homogeneous graphs
Symmetry and eigenvectors
structure and symmetry
Cayley graphs and interconnection networks
Some applications of Laplace eigenvalues of graphs
Other editions - View all
2-arc transitive abelian adjacent algebra algorithms Aut(X automorphism group bipartite graph blocks cartesian product Cay(G,S Cayley graphs chromatic number circulant graphs colouring combinatorial complete graph Comput conjecture connected graph construction contains Corollary coset countable cycle defined Definition denote diameter digraph digraph F Discrete Math disjoint distance transitive graphs double ray edge edge-transitive eigenvalues element embedding equivalent example exists finite graphs function G and H graph G graph homomorphisms Graph Theory graphs of order group G Hence homogeneous homomorphism hypercube implies imprimitive induced subgraph infinite integer isomorphic Kneser graphs Lemma length Let F Let G linear locally finite matrix metacirculant orbital graphs pairs partition path Petersen graph polynomial prime primitive problem product of graphs Proof Let Proposition quasiprimitive quotient regular graphs relation result retracts Section self-paired semidefinite programming simple group structure subset symmetric Theorem transposition valency vertex vertex set vertex-transitive graphs VT-graphs wreath product