A study of hypercube graph and its application to parallel computing

Recent studies have shown an increased interest and research in the area of parallel computing. Graphs offer ' an excellent means for the modelling of parallel computers. The hypercube graph is emerging as the preferred topology for parallel processing. It is a subject of intense research and study by both graph theorists and computer scientists.This thesis is intended to investigate several graph theoretic properties of hypercubes and one of its subgraphs (middle graph of the cube). These include edgedensity, diameter, connectivity, Hamiltonian property, Eulerian property, cycle structure, and crossing number.. Theproblem of routing using parallel algorithms for implementing partial permutation is also described. We also discuss the problem of multiplying matrices on hypercube, which is helpful in solving graph theoretic problems like shortest paths and transitive closure. The problem of graph embeddings is also discussed pertaining to hypercube graph. Lastly, several important applications of hypercubes are discussed.