Topological Representation of Graph Isomorphism Types
Abstract
The strategic plan of this research program was to develop the theory of imbedding distributions as a possible probabilistic approach to the graph isomorphism problem. It was projected that, although the much pursued goal of a practical polynomial-time test for graph isomorphism might not be achieved, the expected mathematical development in this novel attempt would provide a suitable return for the investment. It was hoped that 3-connected graphs would prove to be distinguishable with lower invariants in the hierarchy, since there are traceable inductive constructions of the family of all 3-connected graphs. However, algebraic methods of Rieper established that none of the well- understood lower invariants was complete for the 3-connected simple graphs. Thus, obtaining a graph isomorphism test by this avenue seems to involve either rising in the hierarchy of invariants or identifying a nearly exhaustive class of graphs for which the lower invariants are complete.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 20, 1991
- Accession Number
- ADA243528
Entities
People
- Jonathan L. Gross
Organizations
- Columbia University