Graphs, Partitions and Cosets: G-Graphs and Their Applications

Interactions between graph theory and group theory have already led to interesting results for both domains. For example, every finite group is isomorphic to the automorphism group of a finite graph. The most famous example of graphs constructed from groups are Cayley graphs, that revealed to be particularly interesting from both a theoretical and practical point if view. If the regularity of Cayley graphs is one of the motivations of their large use, it is also a limit as they are not relevant to generate semi-regular networks. G-graphs are a new family of graphs defined from a group and have many regular properties but are less restrictive. These graphs are semi-regular and their regularity and compact representation motivate their study for the analysis and the design of networks or for other application areas such as coding theory. This book proposes to study this class of graphs using an approach based on operational research while most studies on these graphs have so far been dominated by algebraic approaches.