Studies in Informatics and Control – ICI Bucharest
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 (4), 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 U
V 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 v
V is a vertex in G, the neighborhood NG(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]=S
N(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 n1 vertices. If e=xy
E, 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 (A
B=
) 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 A
V 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 Conjecture, 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