Probe split graphsReport as inadecuate

Probe split graphs - Download this document for free, or read online. Document in PDF available to download.

1 Institut für Informatik Rostock

Abstract : An undirected graph G=V,E is a probe split graph if its vertex set can be partitioned into two sets, N non-probes and P probes where N is independent and there exists E- ⊆ N× N such that G-=V,E∪ E- is a split graph. Recently Chang et al. gave an OV4V+E time recognition algorithm for probe split graphs. In this article we give OV2+VE time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.

Author: Van Bang Le - H. N. Ridder -



Related documents