Automorphism groups of some families of bipartite graphs

Abstract

This paper discusses the automorphism group of a class of weakly semiregular bipartite graphs and its subclass called WSBEND graphs. It also tries to analyse the automorphism group of the SM sum graphs and SM balancing graphs. These graphs are weakly semiregular bipartite graphs too. The SM sum graphs are particular cases of bipartite Kneser graphs. The bipartite Kneser type graphs are defined on n-sets for a fixed positive integer n. The automorphism groups of the bipartite Kneser type graphs are related to that of weakly semiregular bipartite graphs. Weakly semiregular bipartite graphs in which the neighbourhoods of the vertices in the SD part having the same degree sequence, possess non trivial automorphisms. The automorphism groups of SM sum graphs are isomorphic to the symmetric groups. The relationship between the automorphism groups of SM balancing graphs and symmetric groups are established here. It has been observed by using the well known algorithm Nauty, that the size of automorphism groups of SM balancing graphs are prodigious. Every weakly semiregular bipartite graphs with k-NSD subparts has a matching which saturates the smaller partition.

Keywords

• sm sum graphs, weakly semiregular bipartite, automorphism, symmetric groups, kneser graphs, simple groups