**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.

**1. Introduction**

Throughout this paper *G*=(*V*,*E*) is a simple (i.e. finite, undirected, without loops and multiple edges) graph [2]. Let *co*– denote the complement graph of *G*. For *UV* let *G*(*U*) denote the subgraph of *G* induced by *U*. By *G*–*X* we mean the graph *G*(*V*–*X*), whenever *XV*, but we often denote it simply by *G*–*v* (*V*) when there is no ambiguity. If *vV* is a vertex in *G*, the neighborhood *N _{G}*(n)denotes the vertices of

*G*–

*v*that are adjacent to

*v*. We write

*N*(

*v*) when the graph

*G*appears clearly from the context. The neighborhood of the vertex

*v*in the complement of the graph

*G*is denoted by . For any subset

*S*of vertices in the graph

*G*the neighborhood of

*S*is and

*N*[

*S*]=

*SN*(

*S*). A clique is a subset of

*V*with the property that all the vertices are pairwise adjacent. The

*clique*

*number*(

*density*) of

*G*, denoted by (

*G*) is the cardinal of the maximum clique. A clique cover is a partition of the vertices set such that each part is a clique. (

*G*) is the cardinal of a smallest possible clique cover of

*G*; it is called the

*clique*

*cover*

*number*of

*G*. A

*stable*(or

*independent*) set is a subset of V with the property that all the vertices are pairwise non-adjacent. The

*stability*

*number*of

*G*is (

*G*)=; the

*chromatic*

*number*of

*G*is (

*G*)=.

A *dominating set* for a graph *G *= (*V*, *E*) is a subset *D* of *V* such that every vertex not in *D* is joined to at least one member of *D* by some edge. The *domination number* γ(*G*) is the number of vertices in a smallest dominating set for *G*.

By we mean a chordless path on *n*3 vertices, the chordless cycle on *n*3 vertices, and the complete graph on *n*1 vertices. If *e*=*xyE*, we also denote *x~y*; we also denote *x*≁*y* whenever *x*, *y* are not adjacent in *G*. A set *A* is totally adjacent (non adjacent) with a set *B* of vertices (*AB*=) if *ab* is (is not) edge, for any *a* vertex in *A* and any *b* vertex in *B*; we note denote *A~B* (*A≁B*). A graph *G* is *F*-free if none of its induced subgraphs is in *F*.

The subset *AV* is called a *cutset* if *G*–*A* is not connected. If, in addition, none of the proper subsets of *A* is a cutest, then *A* is called a minimal cutset .

The paper is organized as follows. In Section 2 we give preliminary results. In Section 3 we give a characterization of weak-bisplit graphs.

**References**:

- BRANDSTAEDT, A., P. L. HAMMER, V. B. LE, V. V. LOZIN,
**Bisplit Graphs**, Rutcor Research Report RRR 28-2002, http://rutcor.rutgers.edu/pub/rrr/reports2002/28_2002.ps. - BERGE, C.,
**Graphs**, North-Holland, Amsterdam. 1985. - FOUQUET, J. L., V. GIAKOUMAKIS, J. M. VANHERPE,
**Bipartite Graphs Totally Decomposable by Canonical Decomposition**, Intl. J. Foundations Comput. Sci. 10, 1999, pp. 513-533. - FOUQUET, J. L., J. M. VANHERPE,
**On Bipartite Graphs with Weak Density of Some Subgraphs**, Discrete Mathematics 307, 2007, pp. 1516-1524. **GIAKOUMAKIS,**V.,**J. M. VANHERPE**,**Linear Time Recognition of Weak Bisplit Graphs**, Electronic Notes in Discrete Mathematics, 5, 2000, pp. 138-141.- GOLUMBIC, M. C., R. UDI,
**On the Clique-width of Perfect Graph Classes (extended abstract)**, Lect. Notes Comput. Sci. 1665, 1999, pp. 135-147. - HAIKO, M, A. BRANDSTAEDT,
**The NP-completeness of Steiner Tree and Dominating Set for Chordal Bipartite Graphs**, Theor. Comput. Sci. 53, 1987, pp. 257-265. - POLJAK, S.,
**A Note on the Stable Sets and Coloring of Graphs**, Comment. Math. Univ. Carolin. 15, 1974, pp. 307-309. - STANOJEVIC, M., M. VUJOŠEVIC, B. STANOJEVIC,
**Computation Results of Finding All Efficient Points in Multiobjective Combinatorial Optimization**, Intl. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844, Vol. III, 2008, No. 4, pp. 374-383. - TALMACIU, M.,
**Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization**– Ph. D. Thesis, University “Al. I. Cuza” Iasi, Romania, 2002. - TALMACIU, M., E. NECHITA,
**Recognition Algorithm for Diamond-free Graphs**, Informatica, 18, 2007, pp. 457-462. - TALMACIU, M; E. NECHITA, G. C. CRISAN,
**A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjectur****e**, Studies in Informatics and Control, 18, 2009, pp. 349-354. - http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_444.html
- http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_457.html