Graph Isomorphism, General Remarks

An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative computational complexity of generalizations and restrictions of the graph isomorphism problem. In the first Section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say Tarski models from logic). Then we show that valence seems to be important. Finally we analyze symmetric cubic graphs.

Authors

• Gary L. Miller

Keywords

No keywords are indexed for this paper.