Return to search

Uniqueness of Bipartite Factors in Prime Factorizations Over the Direct Product of Graphs

While it has been known for some time that connected non-bipartite graphs have unique prime factorizations over the direct product, the same cannot be said of bipartite graphs. This is somewhat vexing, as bipartite graphs do have unique prime factorizations over other graph products (the Cartesian product, for example). However, it is fairly easy to show that a connected bipartite graph has only one prime bipartite factor, which begs the question: is such a prime bipartite factor unique? In other words, although a connected bipartite graph may have multiple prime factorizations over the direct product, do such factorizations contain the same prime bipartite factor? It has previously been shown by Hammack that when the prime bipartite factor is K_2, this is in fact true. The goal of this paper is to prove that this is in fact true for any prime bipartite factor, provided the graph being factored is R-thin. The proof of the main result takes the same initial approach as the proof by Hammack, before moving into new territory in order to prove the final result.

Identiferoai:union.ndltd.org:vcu.edu/oai:scholarscompass.vcu.edu:etd-4016
Date25 April 2013
CreatorsPuffenberger, Owen
PublisherVCU Scholars Compass
Source SetsVirginia Commonwealth University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceTheses and Dissertations
Rights© The Author

Page generated in 0.0017 seconds