Biclique graphs of interval bigraphs. (English) Zbl 1440.05132
Summary: The biclique graph \( K B ( G )\) is the intersection graph of all the bicliques of a graph \(G\). The aim of our work is to recognize graphs that are biclique graphs of interval bigraphs \(( \mathcal{IBG} )\). In this paper we prove that \(K B ( \mathcal{IBG} ) \subset K_{1 , 4} \)-free co-comparability graphs. We also study the class of biclique graphs of proper interval bigraphs \(( \mathcal{PIB} )\). Recall that \(\mathcal{PIB}\) is equal to the class of bipartite permutation graphs \(( \mathcal{BPG} )\). We present a characterization of the class \(K B ( \mathcal{PIB} )\) and of the biclique graphs of a subclass of \(\mathcal{PIB}\) that leads to a polynomial time recognition algorithm. We also present characterizations of biclique graphs of some classes such as complete graphs, trees and graphs with girth at least 5.
MSC:
| 05C38 | Paths and cycles |
Keywords:
bicliques; biclique graphs; interval bigraphs; bipartite permutation graphs; co-comparability graphsSoftware:
ILIGRAReferences:
| [1] | Gowtham Atluri, Jeremy Bellay, Gaurav Pandey, Chad Myers, Vipin Kumar, Discovering coherent value bicliques in genetic interaction data. in: Proceedings of 9th International Workshop on Data Mining in Bioinformatics, BIOKDD’10, 2010, pp. 125-132. |
| [2] | Bondy, A.; Durán, G.; Lin, M.; Szwarcfiter, J., Self-clique graphs and matrix permutations, J. Graph Theory, 44, 3, 178-192 (2003) · Zbl 1031.05115 |
| [3] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA) · Zbl 0919.05001 |
| [4] | Bu, Dongbo; Zhao, Yi; Cai, Lun; Xue, Hong; Zhu, Xiaopeng; Lu, Hongchao; Zhang, Jingfen; Sun, Shiwei; Ling, Lunjiang; Zhang, Nan; Li, Guojie; Chen, Runsheng, Topological structure analysis of the protein-protein interaction network in budding yeast, Nucleic Acids Res., 31, 9, 2443-2450 (2003) |
| [5] | Durán, G.; Lin, M. C., Clique graphs of helly circular-arc graphs, Ars Combin., 60, 255-271 (2001) · Zbl 1072.05565 |
| [6] | Farzad, Babak; Lau, Lap Chi; Le, Van Bang; Tuy, Nguyen Ngoc, Complexity of finding graph roots with girth conditions, Algorithmica, 62, 1-2, 38-53 (2012) · Zbl 1239.05127 |
| [7] | Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003 |
| [8] | Groshaus, Marina E., Bicliques, cliques, neighborhoods y la propiedad de Helly (2006), Universidad de Buenos Aires, (Ph.D. thesis) |
| [9] | Groshaus, Marina; Guedes, André L. P.; Montero, Leandro, Almost every graph is divergent under the biclique operator, Discrete Appl. Math., 201, 130-140 (2016) · Zbl 1329.05280 |
| [10] | M. Groshaus, A. Guedes, J.P. Puppo, The biclique graph of a subclass of split graphs, in: Latin American Workshop on cliques in graphs, La Plata, Argentina, 2016, pp. 22. · Zbl 1383.05235 |
| [11] | Groshaus, Marina E.; Montero, Leandro P., The number of convergent graphs under the biclique operator with no twin vertices is finite, (LAGOS’09 - V Latin-aMerican Algorithms, Graphs and Optimization Symposium. LAGOS’09 - V Latin-aMerican Algorithms, Graphs and Optimization Symposium, Electron. Notes Discrete Math., vol. 35 (2009), Elsevier Sci. B. V.: Elsevier Sci. B. V. Amsterdam), 241-246 · Zbl 1268.05107 |
| [12] | Groshaus, M.; Montero, L., On the iterated biclique operator, J. Graph Theory, 73, 2, 181-190 (2013) · Zbl 1262.05117 |
| [13] | Groshaus, Marina; Szwarcfiter, Jayme L., Biclique graphs and biclique matrices, J. Graph Theory, 63, 1, 1-16 (2010) · Zbl 1216.05104 |
| [14] | Haemers, Willem H., Bicliques and eigenvalues, J. Combin. Theory Ser. B, 82, 1, 56-66 (2001) · Zbl 1028.05066 |
| [15] | Harary, Frank, (Graph Theory. Graph Theory, Addison-Wesley Series in Mathematics (1969), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA) · Zbl 0182.57702 |
| [16] | Harary, Frank; Kabell, Jerald A.; McMorris, Frederick R., Bipartite intersection graphs, Comment. Math. Univ. Carolin., 023, 4, 739-745 (1982) · Zbl 0516.05049 |
| [17] | Hedman, Bruce, Clique graphs of time graphs, J. Combin. Theory Ser. B, 37, 3, 270-278 (1984) · Zbl 0547.05056 |
| [18] | Hell, Pavol; Huang, Jing, Interval bigraphs and circular arc graphs, J. Graph Theory, 46, 313-327 (2004) · Zbl 1046.05066 |
| [19] | R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Trawling the web for emerging cyber-communities. in: Proceeding of the 8th international conference on World Wide Web, 1999, pp. 1481-1493. |
| [20] | Larrion, F.; Neumann-Lara, V., On clique divergent graphs with linear growth, Discrete Math., 245, 1, 139-153 (2002) · Zbl 0993.05143 |
| [21] | Lehot, P. G.H., An optimal algorithm to detect a line graph and output its root graph, J. ACM, 21, 4, 569-575 (1974) · Zbl 0295.05118 |
| [22] | Lin, Yaw-Ling; Skiena, Steven S., Algorithms for square roots of graphs, SIAM J. Discrete Math., 8, 1, 99-118 (1995) · Zbl 0821.05052 |
| [23] | Lin, M.; Soulignac, F.; Szwarcfiter, J., The clique operator on circular-arc graphs, Discrete Appl. Math., 158, 12, 1259-1267 (2010) · Zbl 1209.05246 |
| [24] | Liu, Guimei; Sim, Kelvin; Li, Jinyan, Efficient mining of large maximal bicliques, (Proceedings of the 8th International Conference on Data Warehousing and Knowledge Discovery. Proceedings of the 8th International Conference on Data Warehousing and Knowledge Discovery, DaWaK’06 (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 437-448 |
| [25] | Liu, Dajie; Trajanovski, Stojan; Mieghem, Piet Van, ILIGRA: An efficient inverse line graph algorithm, J. Math. Model. Algorithms Oper. Res., 14, 1, 13-33 (2015) · Zbl 1347.05239 |
| [26] | Motwani, Rajeev; Sudan, Madhu, Computing roots of graphs is hard, Discrete Appl. Math., 54, 1, 81-88 (1994) · Zbl 0812.68103 |
| [27] | Müller, Haiko, Recognizing interval digraphs and interval bigraphs in polynomial time, Discrete Appl. Math., 78, 1-3, 189-205 (1997) · Zbl 0890.68103 |
| [28] | Nagarajan, Niranjan; Kingsford, Carl, Uncovering genomic reassortments among influenza strains by enumerating maximal bicliques, (2008 IEEE International Conference on Bioinformatics and Biomedicine (2008), IEEE Computer Society), 223-230 |
| [29] | Prisner, E.; Szwarcfiter, J. L., Recognizing clique graphs of directed and rooted path graphs, Discrete Appl. Math., 94, 321-328 (1999) · Zbl 0927.05071 |
| [30] | Roussopoulos, Nicholas D., A max m, n algorithm for determining the graph h from its line graph g, Inform. Process. Lett., 2, 4, 108-112 (1973) · Zbl 0274.05116 |
| [31] | Spinrad, Jeremy; Brandstädt, Andreas; Stewart, Lorna, Bipartite permutation graphs, Discrete Appl. Math., 18, 3, 279-292 (1987) · Zbl 0628.05055 |
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.
