Isomorphism Testing in Hookup Classes

Authors:
  • MKM. M. Klawe
    M. M. Klawe
  • DCD. G. Corneil
    D. G. Corneil
  • APA. Proskurowski
    A. Proskurowski

Abstract
Hookup classes are classes of graphs with a certain type of recursive definition, which can be viewed as a generalization of k-trees. We show that many hookup classes of graphs are isomorphism complete, and give polynomial isomorphism algorithms for the others. Other results in this paper include the development of a structural decomposition for hookup graphs and similar isomorphism results for generalizations of hookup classes, including a polynomial isomorphism testing algorithm for chordal graphs with bounded maximum clique size.