Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512602 | Discrete Mathematics | 2005 | 22 Pages |
Abstract
An undirected graph G=(V,E) is a bisplit graph if its vertex set can be partitioned into a stable set and a complete bipartite graph. We provide an O(|V||E|) time recognition algorithm for these graphs and characterize them in terms of forbidden induced subgraphs. We also discuss the problem of recognizing whether G has a stable set S such that the connected components of G[V⧹S] are more than one complete bipartite subgraph.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andreas Brandstädt, Peter L. Hammer, Van Bang Le, Vadim V. Lozin,