ON BICLIQUES, BICLIQUE PARTITIONS AND RELATED CLASSES OF COGRAPHS
MIHAI TALMACIU Department of Mathematics, Informatics and Education Sciences, Faculty of Sciences, "Vasile Alecsandri" University of Bacău, Calea Mărăşeşti 157, Bacău 600115, ROMANIA,
e-mail:mtalmaciu@ub.ro, mihaitalmaciu@yahoo.com
In this article we will highlight the relation between attack graphs, cross associations and biclique partitions. The attack graphs are used to evaluate network security risk. Also, we will give an efficient recognition algorithm for a maximal subclass of cographs (P4-free graphs), we will give the necessary and sufficient conditions for the existence of a bicli-que partition and we will determine some combinatorial optimzation numbers for some classes of graphs (maximum subclasses for P4-free) in efficient time. Also, we will deter-mine maximum bicliques for a maximal subclass of cographs and we give some applicati-ons of minimal unbreakable graphs in optimization problems and in chemistry. Bicliques (complete bipartite graphs) of graphs have been studied extensively, partially motivated by the large number of applications.
