Some Combinatorial Optimization Problems for Weak-Bisplit Graphs

Mihai TĂLMACIU
University of Bacău, Department of Mathematics and Informatics
8 Spiru Haret, Bacău, Romania

Elena NECHITA
University of Bacău, Department of Mathematics and Informatics
8 Spiru Haret, Bacău, Romania

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.

>>Full text
CITE THIS PAPER AS:
Mihai TĂLMACIU, Elena NECHITA, Some Combinatorial Optimization Problems for Weak-Bisplit Graphs, Studies in Informatics and Control, ISSN 1220-1766, vol. 19 (2), pp. 427-434, 2010.