Quick search
Go!

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

Issue:

SSRSMI, Number 2, Volume XXVI

Section:

Volume 26, Number 2

Abstract:

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.

Keywords:

attack graph, biclique cover, biclique partition, combinatorial optimization numbers, P4-free graphs.

Code [ID]:

SSRSMI201602V26S01A0003 [0004496]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacu