DECOMPOSITIONS OF HYPERCUBE GRAPHS INTO PATHS, CYCLES AND STARS

Abstract

The current research of graph decomposition has been one of the most prominent areas of graph theory, since many combinatorial, algebraic and other mathematical structures are linked to graph decomposition which makes their research a great theoretical importance. In addition to it, the results of graph decomposition can be used in design of experiments, coding theory, radio astronomy, X-ray crystallography, computer and communication networks and in other fields. The significance of cube graphs is intensively studied in graph theory and the interest in hypercube graphs has been escalated by the recent advent of massively parallel computers whose structure is that of hypercube graphs. The hypercube graph is the generalization of a cube into more dimensions. The hypercube graph topology proposes ample interconnection structures with large bandwidth capabilities, logarithmic diameter measures, and extreme magnitude of fault tolerance. Another intriguing attribute of the hypercube graph is its homogeneity and symmetry. It is understood that from a topological point of view, the hypercube graph facilitates a perfect balance between node connectivity, network diameter, and algorithm embeddability which ultimately makes the programming easier. This balance makes the hypercube graph suitable for a wide class of computationally extensive problems. The above fact motivates the present study on the decomposition of dimensional hypercube graph into paths, cycles, stars and tadpoles. . DECOMPOSITIONS OF HYPERCUBE GRAPHS INTO PATHS, CYCLES AND STARS iv iv  The first chapter focuses on few basic definitions, notations, and review of the results.  The second chapter provides the necessary and sufficient conditions for the existence of a decomposition of hypercube graphs into paths and cycles of length four.  The third chapter furnishes on the necessary and/or sufficient conditions for the existence of a decomposition of hypercube graphs into paths and cycles having k edges.  The fourth chapter investigates and demonstrates the results of the existence of a multidecomposition of hypercube graphs into paths, cycles and stars.  The fifth chapter highlights on the necessary and sufficient conditions for the existence of a decomposition of hypercube graphs into tadpoles.