| Full text | |
| Author(s): |
Pedrotti, Vagner
;
de Mello, Celia Picinin
Total Authors: 2
|
| Document type: | Journal article |
| Source: | DISCRETE APPLIED MATHEMATICS; v. 160, n. 18, p. 9-pg., 2012-12-01. |
| Abstract | |
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 P-4-laden graphs, extending an algorithm for P-4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L Palios, Minimal separators in P-4-sparse graphs, Discrete Math. 306 (3) (2006) 381-392]. We also give bounds on the number and total size of all minimal separators of extended P-4-laden graphs and some of their subclasses, such as P-4-tidy and P-4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered. (C) 2012 Elsevier B.V. All rights reserved. (AU) | |