A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture

Mihai TĂLMACIU, Elena NECHITA, Gloria-Cerasela CRIŞAN
University of Bacău, Department of Mathematics and Informatics
8 Spiru Haret, Bacău, ROMANIA

Abstract: A graph is normal if admits a clique cover and a stable set cover so that every clique may intersect every stable set. The Normal Graph Conjecture says that every {,,}-free graph is normal. In this paper we prove this conjecture for the class of O-graphs and we give a recognition algorithm for O-graphs.

Keywords: Normal graphs, O-graphs, Partitionable graphs, Partite graphs, Triangulated graphs.

Mihai Tălmaciu received his M.S. degree in Informatics from Alexandru Ioan Cuza University, Iaşi, Romania, in 1976 and the his Ph.D. degree in Information Sciences from the same institution in 2002. He is a Professor of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. His areas of research include Combinatorics and Graphs Theory, Graph Algorithms and Numerical Analysis.

Elena Nechita received her M.S. degree in Informatics from Alexandru Ioan Cuza University, Iaşi, Romania, in 1987 and her Ph.D. degree in Information Sciences from the same institution in 2000. She is an Associate Professor of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. Her areas of research include: Probability Theory, Artificial Intelligence and Evolutionary Computing.

Gloria-Cerasela Crişan received her M.S. degree in Informatics from University of Bucharest, Romania, in 1986 and the Ph.D. degree in Information Sciences from Alexandru Ioan Cuza University, Iaşi, in 2008. She is a Lecturer of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. Her areas of research include Artificial Intelligence and Evolutionary Computing.

>>Full text
CITE THIS PAPER AS:
Mihai TĂLMACIU, Elena NECHITA, Gloria-Cerasela CRIŞAN, A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (4), pp. 349-354, 2009.

1. Introduction

Normal graphs form a superclass of perfect graphs and can be considered as closure of perfect graphs by means of co-normal products [9] and graph entropy [8]. Perfect graphs have been characterized as those without odd holes and antiholes as induced subgraphs (Strong Perfect Graph Theorem, [5]). Korner and de Simone [6] observed that C₅,C₇, are minimal, not normal graphs. As a generalization of the Strong Perfect Graph Theorem, Korner and de Simone conjectured that every {C₅,C₇,}-free graph is normal (Normal Graph Conjecture, [11]). Wagler [15] proved the conjecture for the class of circulant graphs.

The entropy [10] of a graph is a functional depending both one the graph itself and on a probability distribution on its vertex set.

In [4] we find a recent survey of results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution.

In [8], the authors prove that a graphs is perfect if and only if it “splits graph entropy”. Using this derive the following strengthening of the normality of perfect graphs:

Let G be a perfect graph. Then G contains a family A of independent sets and a family B of cliques with the following properties:

i) |A|+|B|=k+1;

ii) the sets in A (B) cover all vertices;

iii) the incidence vectors of sets in A (B) are linearly independent;

iv) every AÎ A intersects every BÎ B.

The class of perfect graphs is important because many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs [6].

Partitionable graphs contain all the potential counterexemples to Berge’s famous Strong Perfect Graph Conjecture ([3]) which was proved by Chudnovski, Robertson, Seymour, and Thomas in [5]. Partitionable graphs ([7]) are one of the central objects in the theory of perfect graphs due to the following theorem of Lovasz: A graph is perfect if and only if a (H)w (H)³ n(H) for every induced subgraph H of G.

In this paper we find a class of partitionable graphs that are not perfect, but are normal. We prove Normal Graph Conjecture for the class of O-graphs and give a recognition algorithm for O-graphs.

Throughout this paper, G=(V,E) is a simple (i.e. finite, undirected, without loops and multiple edges) graph [2]. Let 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 XÍ V, but we often denote it simply by G–v (“ n Î 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 (n). For any subset S of vertices in G, the neighborhood of S is N(S)=È n Î _SN(n)–S 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 w (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. q (G) is the cardinal of a smallest possible clique cover of G; it is called the clique cover number of G. The stability number of G is a (G)=; the chromatic number of G is c (G)=.

By P_n, C_n, K_n 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=xyÎ E, we also write x~y; we also write 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=f) if ab is (is not) edge, for any a vertex in A and any b vertex in B; we note with A~B (A≁B). A graph G is F-free if none of its induced subgraphs is in F.

A graph G is called a –partitionable if

a (G)=q (G) holds.

A graph G is perfect if a (H)=q (H) (or, equivalent, c (H)=w (H)) holds for every induced subgraph H of G, i.e. every induced subgraph is a-partitionable.

We call matching a set FÌ E such that the edges in F are not adjacent.

A [p,q,r]-partite graph is a graph whose set of vertices is partitioned in p stable sets S₁,S₂,…,S_p, each of them consisting of exactly q vertices and every subgraph induced by S_iÈS_j consists of exactly r independent edges, for 1£ i<j£ p.

A circulant C^k,n is a graph with nodes 1,…,n where ij is an edge if i and j differ by at most k(mod n) and i¹ j.

The subset AÌ V is called a cutset if G–A is not connected. If, in addition, some vÎ A is adjacent to every vertex in A-{v}, then A is called a star cutset and v is called the center of A.

The paper is organized as follows. In Section 2 we give sufficient conditions for a graph to be normal. In Section 3 we give a recognition algorithm for O-graphs.

4. Conclusions and Future Work

In this paper we have proved that the normal graph conjecture is true for O-graphs and we have presented a recognition algorithm for these graphs.

Our future work will verify the conjecture on classes of graphs characterized by means of forbidden subgraphs.

References:

Balas, E., C. S. Yu, Finding a Maximum Clique in an Arbitrary Graph. SIAM Journal of Computing 15, 1986, pp. 1054-1068.
Berge, C., Graphs, North-Holland, Amsterdam. 1985.
Boros, E., V. Gurvich, S. Hougardy, Recursive Generation of Partitionable Graphs, http://www2. informatik.hu-berlin.d/~hougardy/paper /BGH-JGT.pdf, 2002.
Cardinal, J., S. Fiorini, G. Jeret, Minimum Entropy Combinatorial Optimization Problems, Lecture Notes in Computer Science, 2009, pp. 79-88.
Chudnovski, M., N. Robertson, P. D. Seymour, R. Thomas, Strong Perfect Graphs Theory, Annals of Mathematics 164, 2006, pp. 51-229.
Chudnovski, M., N. Robertson, P. D. Seymour, R. Thomas, Progress on Perfect Graphs, Mathematical Programming Ser. B 97, 2003, pp. 405-422.
Conforti, M., G. Cornuejols, G. Gasparyan, K. Vuskovic, Perfect Graphs, Partitionable Graphs and Cutset, Combinatorica 22(1), 2002, pp. 19-33.
Csiszar, I., J. Korner, L. Lovasz, K. Marton, G. Simonyi, Entropy Splitting for Antiblocking Corners and Perfect Graphs, Combinatorica 10, 1990, pp. 27-40.
Korner, J., An Extension of the Class of Perfect Graphs, Studia Scientiarum Mathematicarum Hungarica 8, 1973, pp. 405-409.
Korner, J. K. Marton, Graphs that Split Entropies, SIAM J. Discrete Math. Volume 1, 1988, pp. 77-79.
Korner, J., C. de Simone, On the Odd Cycles of Normal Graphs, Discrete Applied Mathematics 94, 1999, pp. 161-169.
Olaru, E., M. Talmaciu, A Class of Partitionable Graphs, Bull. Math. Soc. Sc. Math. Roumanie, Tome 48(96), No. 3, 2005, pp. 313-317.
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, Vol. 18, No. 3, 2007, pp. 457-462.
Wagler A. K., The Normal Graph Conjecture is True for Circulant Graphs. Tehnical Raport ZR, 2004, pp. 04-06, ZIB.
Warren, J. S., I. V. Hicks, (2006) Combinatorial Branch-and-Bound for the Maximum Weight Independent Set Problem, http://ie.tamu.edu/People/ faculty/Hicks/jeff.rev.pdf, working paper, accesed July 10, 2009.