Graphs find extensive applications in various fields of information sciences. Graph models can efficiently represent many physical situati-ons and relationships between pieces of information. So, one can use graphs to solve several practical problems.
An interconnection network is a network of links between a coll-ection of processors and memory units. Interconnection networks play an essential role in overall parallel system performance. So in any pr-oposed or existing parallel processing architectures, an interconnec-tion network is used to realize the transportation of data between processors or between processors and memory modules. The multidi-mensional tori, k-ary r-cubes, and hypercubes are popular intercon-nection networks.