Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651433 | Discrete Mathematics | 2006 | 12 Pages |
Abstract
In this paper, we determine the minimal separators of P4P4-sparse graphs and establish bounds on their number. Specifically, we show that a P4P4-sparse graph G on n vertices and m edges has fewer than 2n/32n/3 minimal separators of total description size at most 4m/34m/3. The bound on the number of minimal separators is tight and is also tight for the class of cographs, a well known subclass of the P4P4-sparse graphs. Our results enable us to present a linear-time and linear-space algorithm for computing the number of minimal separators of a given P4P4-sparse graph; the algorithm can be modified to report the minimal separators of the input graph in linear time and space as well.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stavros D. Nikolopoulos, Leonidas Palios,