A Linear Algorithm to Determine Isomorphsim of Unicyclic Graphs
Sandra Hedetniemi, Terry Beyer
Committee:
Technical Report(May 1980)
Keywords: graph isomorphism, tree encoding, unicyclic graphs, functional digraphs

A linear algorithm is presented for determining the isomorphism of two unicyclic graphs (graphs which are connected and have exactly one cycle). This algorithm is simpler than the general algorithm for planar graphs [9] which could also be applied since it uses the properties of the class of unicyclic graphs. It therefore is easily generalized to the class of functional digraphs. The algorithm uses as a subalgorithm a linear algorithm to uniquely encode a tree as a sequence of integers.