Date of Award
Doctor of Philosophy
We consider hypercubes, median graphs, Cartesian product (sk10-product) of graphs, Kronecker product (x-product) of graphs and Strong product (sk10-product) of graphs from certain algorithmic and combinatorial points of view. Our basic results are the following: (1) We construct certain schemes for partitioning the set of vertices of the n-dimensional hypercube Qn into equal-size maximal independent sets, which lead to an upper bound on the minimum cardinality of a maximal independent set of Qn. Our lower and upper bounds are within a factor of two, and for n = 2[superscript]k - 1, k ≥ 1, the two bounds coincide and hence yield the optimal value. These bounds are correct also for the domination number of Qn. (2) We present two algorithms, each of which recognizes median graphs in time O(n[superscript]2log n). These are based on two different characterizations of median graphs given respectively by Bandelt and Mulder. This improves the previously best-known bound of O(n[superscript]4) of an algorithm of Chung, Graham and Saks. (3) We present two O(n[superscript]2log n) algorithms, each of which obtains an isometric embedding of a given median graph in a hypercube of least possible dimension. These have structures similar respectively to those of the recognition algorithms mentioned above. (4) We state and prove characterizations for the following: planarity of the sk10-product of graphs, and outerplanarity of the sk10-product of graphs and outerplanarity of the x-product of graphs. (5) For the three graph products, we discuss (i) bounds on the following topological invariants: chromatic numbers, independence numbers, domination numbers and clique numbers in terms of the invariants of the factor graphs, and (ii) conditions for the existence of Hamiltonian paths/cycles. This includes an improved lower bound on the independence number of the sk10-product and sufficient conditions for the existence of a Hamiltonian cycle in the x-product.
Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/
Pranava Kumar Jha
Jha, Pranava Kumar, "Hypercubes, median graphs and products of graphs: some algorithmic and combinatorial results " (1990). Retrospective Theses and Dissertations. 9445.