×

zbMATH — the first resource for mathematics

Biclique graphs and biclique matrices. (English) Zbl 1216.05104
Summary: A biclique of a graph \(G\) is a maximal induced complete bipartite subgraph of \(G\). Given a graph \(G\), the biclique matrix of \(G\) is a \(\{0,1,-1\}\) matrix having one row for each biclique and one column for each vertex of \(G\), and such that a pair of \(1, -1\) entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore’s characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of \(G\). Using the concept of biclique matrices, we describe a Krausz-type characterization of biclique graphs. Finally, we show that every induced \(P_{3}\) of a biclique graph must be included in a diamond or in a 3-fan and we also characterize biclique graphs of bipartite graphs.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alexe, Consensus algorithms for the generation of all maximal bicliques, Discrete Appl Math 145 (1) pp 11– (2004) · Zbl 1056.05132
[2] Amilhastre, Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs, Discrete Appl Math 86 (2â3) pp 125– (1998) · Zbl 0906.05067
[3] Lin, Self-clique graphs and matrix permutations, J Graph Theory 44 (3) pp 178– (2003) · Zbl 1031.05115
[4] Booth, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J Comput System Sci 13 (3) pp 335– (1976) · Zbl 0367.68034
[5] BrandstÃ{\currency}dt, SIAM Monographs on Discrete Mathematics and Applications (1999)
[6] Dias, Generating bicliques of a graph in lexicographic order, Theoret Comput Sci 337 (1â3) pp 240– (2005) · Zbl 1076.68048
[7] Escalante, Ãber iterierte Clique-Graphen, Abh Math Sem Univ Hamburg 39 pp 59– (1973)
[8] Fulkerson, Incidence matrices and interval graphs, Pacific J Math 15 pp 835– (1965) · Zbl 0132.21001
[9] Gavril, Algorithms on circular-arc graphs, Networks 4 pp 357– (1974) · Zbl 0309.05126
[10] Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J Combinatorial Theory Ser B 16 pp 47– (1974) · Zbl 0266.05101
[11] Gilmore, Families of sets with faithful graph representations, IBM Research Note N. C. 184 (1962)
[12] Gilmore, A characterization of comparability graphs and of interval graphs, Canad J Math 16 pp 539– (1964) · Zbl 0121.26003
[13] Golumbic, Perfect elimination and chordal bipartite graphs, J Graph Theory 2 (2) pp 155– (1978) · Zbl 0411.05060
[14] Groshaus, Biclique-Helly graphs, Graphs Combinatorics 26 (6) pp 633– (2007) · Zbl 1140.05314
[15] Groshaus, On hereditary Helly classes of graphs, Discrete Math Theor Comput Sci 10 (1) pp 71– (2008) · Zbl 1153.05059
[16] LarriÃ{\({}^3\)}n, A hierarchy of self-clique graphs, Discrete Math 282 (1â3) pp 193– (2004)
[17] Lehot, An optimal algorithm to detect a line graph and output its root graph, J ACM 21 (4) pp 569– (1974) · Zbl 0295.05118
[18] McKee, SIAM Monographs on Discrete Mathematics and Applications (1999)
[19] L. Montero, Convergencia y divergencia del grafo biclique iterado, Master’s thesis, Departamento de ComputaciÃ{\({}^3\)}n, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, 2008.
[20] MÃ{\(\tfrac14\)}ller, On edge perfectness and classes of bipartite graphs, Discrete Math 149 (1â3) pp 159– (1996)
[21] Peeters, The maximum edge biclique problem is NP-complete, Discrete Appl Math 131 (3) pp 651– (2003) · Zbl 1026.68068
[22] Prisner, Graph Theoretic Concepts in Computer Science (Berlin, 1997) pp 273– (1997)
[23] Prisner, Bicliques in graphs. I. Bounds on their number, Combinatorica 20 (1) pp 109– (2000) · Zbl 0980.05033
[24] Roberts, A characterization of clique graphs, J Combinatorial Theory Ser B 10 pp 102– (1971) · Zbl 0215.05801
[25] Tuza, Covering of graphs by complete bipartite subgraphs: Complexity of 0â1 matrices, Combinatorica 4 (1) pp 111– (1984) · Zbl 0559.05050
[26] Yannakakis, STOC ’78: Proceedings of the 10th Annual ACM Symposium on Theory of Computing pp 253– (1978)
[27] Yannakakis, Node-deletion problems on bipartite graphs, SIAM J Comput 10 (2) pp 310– (1981) · Zbl 0468.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.