×

On edge-sets of bicliques in graphs. (English) Zbl 1254.05138

Summary: A biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques.
We characterize graphs whose edge-biclique hypergraph is conformal (i.e., it is the clique hypergraph of its 2-section) by means of a single forbidden induced obstruction, the triangular prism. Using this result, we characterize graphs whose edge-biclique hypergraph is Helly and provide a polynomial time recognition algorithm.
We further study a hereditary version of this property and show that it also admits polynomial time recognition, and, in fact, is characterized by a finite set of forbidden induced subgraphs. We conclude by describing some interesting properties of the 2-section graph of the edge-biclique hypergraph.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alcón, L.; Faria, L.; de Figueiredo, C. M.; Gutierrez, M., The complexity of clique graph recognition, Theoretical Computer Science, 410, 2072-2083 (2009) · Zbl 1168.68015
[2] Beineke, L. W., Characterizations of derived graphs, Journal of Combinatorial Theory, 9, 129-135 (1970) · Zbl 0202.55702
[3] Berge, C., Hypergraphs, North-Holland Mathematical Library, vol. 45 (1989), Elsevier Science Publishers B.V: Elsevier Science Publishers B.V Amsterdam
[4] Calamoneri, T.; Petreschi, R., Edge-clique graphs and the \(\lambda \)-coloring problem, Journal of the Brazilian Computer Society, 7, 38-47 (2001)
[5] Cerioli, M. R., Clique graphs and edge-clique graphs, Electronic Notes in Discrete Mathematics, 13, 34-37 (2003) · Zbl 1075.05572
[6] Cerioli, M. R.; Szwarcfiter, J., Edge clique graphs and some classes of chordal graphs, Discrete Mathematics, 242, 31-39 (2002) · Zbl 0997.05083
[7] M.R. Cerioli, J. Szwarcfiter, A characterization of edge clique graphs, manuscript.; M.R. Cerioli, J. Szwarcfiter, A characterization of edge clique graphs, manuscript. · Zbl 1071.05565
[8] Chartrand, G.; Kapoor, S. F.; McKee, T. A.; Saba, F., Edge clique graphs, Graphs and Combinatorics, 7, 253-264 (1991) · Zbl 0756.05066
[9] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[10] Golumbic, M. C.; Jamison, R. E., The edge intersection graphs of paths in a tree, Journal Combinatorial Theory B, 38, 8-22 (1985) · Zbl 0537.05063
[11] Groshaus, M.; Szwarcfiter, J., Biclique-Helly graphs, Graphs and Combinatorics, 23, 633-645 (2007) · Zbl 1140.05314
[12] Groshaus, M.; Szwarcfiter, J., On hereditary Helly classes of graphs, Discrete Mathematics and Theoretical Computer Science, 10, 71-78 (2008) · Zbl 1153.05059
[13] Groshaus, M.; Szwarcfiter, J., Biclique graphs and biclique matrices, Journal of Graph Theory, 63, 1-16 (2010) · Zbl 1216.05104
[14] Harary, F.; Holzmann, C., Line graphs of bipartite graphs, Revista de la Sociedad Matematica de Chile, 1, 19-22 (1974)
[15] Lin, M. C.; Szwarcfiter, J. L., Faster recognition of clique-Helly and hereditary clique-Helly graphs, Information Processing Letters, 103, 40-43 (2007) · Zbl 1183.05059
[16] Prisner, E., Hereditary clique-Helly graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 14, 216-220 (1993) · Zbl 0794.05113
[17] Raychaudhuri, A., Intersection number and edge-clique graphs of chordal and strongly chordal graphs, Congressus Numerantium, 67, 197-204 (1988) · Zbl 0668.05057
[18] Raychaudhuri, A., Edge-clique graphs of some important classes of graphs, Ars Combinatoria, 32, 269-278 (1991) · Zbl 0757.05065
[19] Szpilrajn-Marczewski, E., Sur deux propriétés des classes d’ensembles, Fundamenta Mathematicae, 33, 303-307 (1945) · Zbl 0060.12508
[20] West, D., Introduction to Graph Theory (1996), Prentice Hall · Zbl 0845.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.