# Algebra 2. The symmetric groups Sn by René Schoof

By René Schoof

Similar combinatorics books

Handbook of Algebra Vol III

1998 . .. a great index is incorporated to be able to support a mathematician operating in a space except his personal to discover adequate details at the subject in query.

Additional resources for Algebra 2. The symmetric groups Sn

Example text

However, the graph H is not connected since, for instance, the vertices T and u in H are not joined b y any path. 2. A multigraph is said to be disconnected if it is not connected. 23(b) is disconnected. 7. 23(b). (1) Which vertices are reachable from the vertex r via a path? (2) Which vertices are reachable from the vertex u via a path? (3) Which vertices are reachable from the vertex p via a path? 24. Note that each of them is a connected ‘piece’, and is called a connected component of H. From now on, we simply call a connected component a component.

6 ) Let G be a graph of order 14 and size 30 in which every vertex is of degree 4 or 5. How many vertices of degree 5 does G have? Construct Introduction to Graph Theory 24 one such graph G. (7) Does there exist a multigraph G of order 8 such that S(G) = 0 while A ( G ) = 7? What if ‘multigraph G’ is replaced by ‘graph G’? (8) Characterize the l-regular graphs. (9) Draw all regular graphs of order n, where 2 5 n <_ 6. (10) (i) Does there exist a graph G of order 5 such that S(G) = 1 and A ( G ) = 4?

Given two arbitrary graphs G and H of the same order and same size, is there an ‘efficient’ procedure which enables us to determine whether G H? This problem, known as the Isomorphism Testing Problem, is a very difficult problem, and until now, only little progress has been made. There are many practical applications which desire a fast procedure to test graph isomorphism. For example, organic chemists who routinely deal with graphs which represent molecular links would like some system to quickly give each graph a unique name.