Degree Type

Dissertation

Date of Award

1990

Degree Name

Doctor of Philosophy

Department

Computer Science

First Advisor

Giora Slutzki

Abstract

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.

DOI

https://doi.org/10.31274/rtd-180813-12503

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Pranava Kumar Jha

Language

en

Proquest ID

AAI9101356

File Format

application/pdf

File Size

134 pages

Share

COinS