From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats

The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T, t) whose vertices are labeled as series(1), parallel(0) or prime. However, full information of G is provided by its modular decomposition tree (T, t) only, if G does not contain prime modules. In this case, (T, t) explains G, i.e., {x, y} is an element of E(G) if and only if the lowest common ancestor lca(T)(x, y) of x and y has label 1. This information, however, gets lost whenever (T, t) contains vertices with label prime. In this contribution, we aim at replacing prime vertices in (T, t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N, t).We characterize graphs that can be explained by such level-1 networks (N, t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules induce polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes.In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N, t), i.e., (N, t) contains exactly one cycle C that is rooted at the root rho(N) of N and where rho(N) has exactly two children while every vertex distinct from rho(N) has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N, t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.