Isomorphism Testing in Hookup Classes
Maria M. Klawe, Derek Gordon Corneil, Andrzej Proskurowski · SIAM Journal on Algebraic and Discrete Methods · 1982
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.