Thursday , June 21 2018

Some Combinatorial Optimization Problems for Weak-Bisplit Graphs

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

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
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 coImage1117 denote the complement graph of G. For UImage1118V let G(U) denote the subgraph of G induced by U. By GX we mean the graph G(VX), whenever XImage1118V, but we often denote it simply by Gv (Image1119V) when there is no ambiguity. If vImage1069V is a vertex in G, the neighborhood NG(n)denotes the vertices of Gv 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 Image1120. For any subset S of vertices in the graph G the neighborhood of S is Image1121 and N[S]=SImage1122N(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 Image1123(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. Image1124(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 Image1125(G)=Image1126; the chromatic number of G is Image1127(G)=Image1128.

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 nImage11293 vertices, the chordless cycle on nImage11303 vertices, and the complete graph on nImage11301 vertices. If e=xyImage1131E, we also denote x~y; we also denote xy whenever x, y are not adjacent in G. A set A is totally adjacent (non adjacent) with a set B of vertices (AImage1132B=Image1133) 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 AImage1134V is called a cutset if GA 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.


  1. BRANDSTAEDT, A., P. L. HAMMER, V. B. LE, V. V. LOZIN, Bisplit Graphs, Rutcor Research Report RRR 28-2002,
  2. BERGE, C., Graphs, North-Holland, Amsterdam. 1985.
  3. 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.
  4. FOUQUET, J. L., J. M. VANHERPE, On Bipartite Graphs with Weak Density of Some Subgraphs, Discrete Mathematics 307, 2007, pp. 1516-1524.
  5. GIAKOUMAKIS, V., J. M. VANHERPE, Linear Time Recognition of Weak Bisplit Graphs, Electronic Notes in Discrete Mathematics, 5, 2000, pp. 138-141.
  6. GOLUMBIC, M. C., R. UDI, On the Clique-width of Perfect Graph Classes (extended abstract), Lect. Notes Comput. Sci. 1665, 1999, pp. 135-147.
  7. 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.
  8. POLJAK, S., A Note on the Stable Sets and Coloring of Graphs, Comment. Math. Univ. Carolin. 15, 1974, pp. 307-309.
  9. 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.
  10. TALMACIU, M., Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization – Ph. D. Thesis, University “Al. I. Cuza” Iasi, Romania, 2002.
  11. TALMACIU, M., E. NECHITA, Recognition Algorithm for Diamond-free Graphs, Informatica, 18, 2007, pp. 457-462.
  12. TALMACIU, M; E. NECHITA, G. C. CRISAN, A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture, Studies in Informatics and Control, 18, 2009, pp. 349-354.