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

Read Online or Download Algebra 2. The symmetric groups Sn PDF

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.