Structure and recognition of domishold graphs (Q1087562)

Domishold graphs introduced by the reviewer and \textit{P. L. Hammer} [Ann. Discrete Math. 3, 1-10 (1978; Zbl 0375.05043)] are here investigated under three related aspects: The first reveals the canonical cell- structure of a domishold graph G with a peculiar threshold supervisor graph on its cells. The second deals with degree sequences of domishold graphs and it is proved that domishold graphs with the same degree sequence are isomorphic. The last yields a recognition algorithm for domisholdness: it is based on the possible cell-structure (easily built) and works in time O(h), where h is the number of cells of the graph.