Some Combinatorial Optimization Problems for Weak-Bisplit Graphs

Mihai Talmaciu, Elena Nechita

Abstract

There exists linear algorithms to recognize weak-bisplit graphs and NP-complete optimization problems are efficiently resolved for this class of graphs. In this paper, using weak-decomposition, we give necessary a sufficient conditions for a graph to be weak-bisplit, bi-cograph, weak-bisplit cograph. We also give an algorithm O(n+m) to determine, the density of a weak-bisplit cograph and we calculate directly the domination number for this class of graphs.

Keywords

Weak-bisplit graphs, Bi-cographs, Weak-bisplit cographs.

View full article