On Module-Composed Graphs.

In this paper we introduce module-composed graphs, i.e. graphs which can be defined by a sequence of one-vertex insertions v₁,...,v_n, such that the neighbourhood of vertex v_i, 2 ≤ i ≤ n, forms a module of the graph defined by vertices v₁,...,v_i − 1. We show that module-composed graphs are HHDS-free and thus homogeneously orderable, weakly chordal, and perfect. Every bipartite distance hereditary graph and every trivially perfect graph is module- composed. We give an ]> time algorithm to decide whether a given graph G = (V,E) is module-composed and construct a corresponding module-sequence. For the case of bipartite graphs, we show that the set of module-composed graphs is equivalent to the well known class of distance hereditary graphs, which implies linear time algorithms for their recognition and construction of a corresponding module-sequence using BFS and Lex-BFS. [ABSTRACT FROM AUTHOR]