Degree Type

Dissertation

Date of Award

2002

Degree Name

Doctor of Philosophy

Department

Mathematics

First Advisor

Clifford Bergman

Abstract

The strong direct product is one of the standard graph products. In 1992, Feigenbaum and Schaffer presented a polynomial-time algorithm to find the unique prime factorization of connected graphs under the strong direct product. In this paper, we show that weakly connected directed graphs have unique prime factorizations with respect to the strong direct product, and we give a polynomial-time algorithm to find the prime factorizations of such digraphs. This is an extension of Feigenbaum and Schaffer's work on factoring undirected graphs under the strong direct product and Imrich's work on factoring undirected graphs with respect to the weak direct product. We also investigate the problem of determining whether an algebra has the congruence extension property. We prove that this problem is complete for polynomial time.

DOI

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

Publisher

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

Copyright Owner

Joy Lynne Becker

Language

en

Proquest ID

AAI3051449

File Format

application/pdf

File Size

47 pages

Included in

Mathematics Commons

Share

COinS