Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653435 | European Journal of Combinatorics | 2015 | 18 Pages |
Abstract
It has long been known that the class of connected nonbipartite graphs (with loops allowed) obeys unique prime factorization over the direct product of graphs. Moreover, it is known that prime factorization is not necessarily unique in the class of connected bipartite graphs.But any prime factorization of a connected bipartite graph has exactly one bipartite factor. It has become folklore in some circles that this prime bipartite factor must be unique among all factorings, but until now this conjecture has withstood proof.This paper presents a proof. We show that if a connected bipartite graph GG has two factorings G≅A×BG≅A×B and G≅A′×B′G≅A′×B′, where BB and B′B′ are prime and bipartite, then B≅B′B≅B′.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Richard Hammack, Owen Puffenberger,