Minimal separators in extended P4 P 4 -ladengraphs
In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P4 P 4 -ladengraphs, extending an algorithm for P4 P 4 -sparsegraphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Minimal separators in P4 P 4 -sparsegraphs, Discrete Math. 306 (3) (2006) 381392]. We also give bounds on the number and total size of all minimal separators of extended P4 P 4 -ladengraphs and some of their subclasses, such as P4 P 4 -tidyand P4 P 4 -litegraphs. Moreover, we show that these bounds are tight for all subclasses considered.
minimal separators primeval decomposition linear-time algorithms modular decomposition graphs with few p4 p 4 s p4 p 4 p4 p 4 p 4