Biclique graphs of split graphs. (English) Zbl 1502.05106
Summary: The biclique graph is the intersection graph of the bicliques of a graph. Its recognition problem is still open. In this paper we study the problem restricted to the class of split graphs. We define a class called nested separable split graphs and solve the recognition problem of biclique graphs of a subclass of the mentioned class. For that, we give a polynomial time algorithm with positive certificate. We also characterize nested split graphs and study properties of biclique graphs of split graphs. For example, we show that they are Hamiltonian. We also present a complexity result for recognizing graphs such that their biclique graphs are complete graphs, that is, we prove that the problem of recognizing biclique-complete graphs in co-NP-complete.
MSC:
| 05C38 | Paths and cycles |
| 05C45 | Eulerian and Hamiltonian graphs |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Aho, A. V.; Garey, M. R.; Ullman, J. D., The transitive reduction of a directed graph, SIAM J. Comput., 1 (1972) · Zbl 0247.05128 |
| [2] | Albano, A.; do Lago, A. P., A convexity upper bound for the number of maximal bicliques of a bipartite graph, Discrete Appl. Math., 165, Supplement C, 12-24 (2014), CTW 2011 · Zbl 1288.05131 |
| [3] | Alcón, L.; Faria, L.; de Figueiredo, C. M.H.; Gutierrez, M., Clique graph recognition is NP-complete, Graph-Theoretic Concepts Comp. Sci., 4271, 269-277 (2006) · Zbl 1167.68403 |
| [4] | 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 |
| [5] | Coudert, D.; Ducoffe, G., On the hyperbolicity of bipartite graphs and intersection graphs, Discrete Appl. Math., 214, Supplement C, 187-195 (2016) · Zbl 1346.05243 |
| [6] | Cruz, E. P.; Groshaus, M.; Guedes, A. L.P.; Puppo, J. P., Biclique graphs of interval bigraphs, Discrete Appl. Math., 281, 134-143 (2020) · Zbl 1440.05132 |
| [7] | Dantas, S.; Groshaus, M.; Guedes, A.; Machado, R. C.S.; Ries, B.; Sasaki, D., On star and biclique edge-colorings, Int. Trans. Operat. Res., 24, 1-2, 339-346 (2017) · Zbl 1358.05100 |
| [8] | Durán, G.; Lin, M. C., Clique graphs of helly circular-arc graphs, Ars Combin., 60, 255-271 (2001) · Zbl 1072.05565 |
| [9] | Groshaus, M.; Guedes, A. L.P.; Montero, L., Almost every graph is divergent under the biclique operator, Discrete Appl. Math., 201, 130-140 (2016) · Zbl 1329.05280 |
| [10] | Groshaus, M. E.; Montero, L. P., The number of convergent graphs under the biclique operator with no twin vertices is finite, (LAGOS’09 - V Latin-aMerican Algorithms. LAGOS’09 - V Latin-aMerican Algorithms, Graphs and Optimization Symposium, volume 35 of Electron. Notes Discrete Math. (2009), Elsevier Sci.: Elsevier Sci. B. V. Amsterdam), 241-246 · Zbl 1268.05107 |
| [11] | Groshaus, M.; Montero, L., On the iterated biclique operator, J. Graph Theory, 73, 2, 181-190 (2013) · Zbl 1262.05117 |
| [12] | Groshaus, M.; Montero, L., Distances between bicliques and structural properties of bicliques in graphs (2019), ArXiv |
| [13] | Groshaus, M.; Szwarcfiter, J. L., Biclique-helly graphs, Graphs Combin., 26, 6, 633-645 (2007) · Zbl 1140.05314 |
| [14] | Groshaus, M.; Szwarcfiter, J. L., Biclique graphs and biclique matrices, J. Graph Theory, 63, 1, 1-16 (2010) · Zbl 1216.05104 |
| [15] | Gutierrez, M., Tree-clique graphs, (Szwarcfiter, J. L., Workshop Internacional de CombinatÓria (1996), Rio de Janeiro: Rio de Janeiro Brazil), 7-26 |
| [16] | Gutierrez, M.; Oubiña, L., Minimum proper interval graphs, Discrete Math., 142, 77-85 (1995) · Zbl 0828.05053 |
| [17] | M. Gutierrez, R. Zucchello, Grafos aci: Una generalización de los grafos de intervalos propios. Manuscript. |
| [18] | Hamelink, R. C., A partial characterization of clique graphs, J. Combin. Theory, 5, 2, 192-197 (1968) · Zbl 0167.22203 |
| [19] | Kershenbaum, A.; Cutillo, A.; Darabos, C.; Murray, K.; Schiaffino, R.; Moore, J. H., Bicliques in graphs with correlated edges: From artificial to biological networks, (Squillero, Giovanni; Burelli, Paolo, Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016,Porto, Portugal, March 30 - April 1, 2016. Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016,Porto, Portugal, March 30 - April 1, 2016, Proceedings, Part I (2016), Springer International Publishing: Springer International Publishing Cham), 138-155 |
| [20] | Larrion, F.; Neumann-Lara, V., On clique divergent graphs with linear growth, Discrete Math., 245, 1, 139-153 (2002) · Zbl 0993.05143 |
| [21] | Legay, S.; Montero, L., On the iterated edge-biclique operator, Electron. Notes Theor. Comput. Sci., 346, 577-587 (2019), The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) · Zbl 07515213 |
| [22] | Lin, M.; Soulignac, F.; Szwarcfiter, J., The clique operator on circular-arc graphs, Discrete Appl. Math., 158, 12, 1259-1267 (2010) · Zbl 1209.05246 |
| [23] | Lu, Y.; Phillips, C. A.; Langston, M. A., Biclique: an r package for maximal biclique enumeration in bipartite graphs, BMC Res. Notes, 13, 1, 88 (2020) |
| [24] | Lucchesi, C. L.; de Mello, C. P.; Szwarcfiter, J. L., On clique-complete graphs, Discrete Math., 183, 1, 247-254 (1998) · Zbl 0894.05045 |
| [25] | Macêdo Filho, H. B.; Machado, R. C.S.; de Figueiredo, C. M.H., Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs, Algorithmica, 77, 3, 786-814 (2017) · Zbl 1359.05043 |
| [26] | Pavlopoulos, G. A.; Kontou, P. I.; Pavlopoulou, A.; Bouyioukos, C.; Markou, E.; Bagos, P. G., Bipartite graphs in systems biology and medicine: a survey of methods and applications, GigaScience, 7, 4 (2018) |
| [27] | Prisner, E., Bicliques in graphs II: Recognizing k-path graphs and underlying graphs of line digraphs, (Möhring, Rolf H., Graph-Theoretic Concepts in Computer Science: 23rd International Workshop, WG’97 Berlin, Germany, June (1997) 18-20 Proceedings (1997), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 273-287 · Zbl 0895.68103 |
| [28] | Roberts, F.; Spencer, J., A characterization of clique graphs, J. Combin. Theory B, 10, 2, 102-108 (1971) · Zbl 0215.05801 |
| [29] | Szwarcfiter, J. L., A survey on clique graphs, (Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics (2003), Springer New York: Springer New York New York, NY), 109-136 · Zbl 1027.05071 |
| [30] | Zhang, Y.; Phillips, C. A.; Rogers, G. L.; E. J.B.; Chesler, E. J.; Langston, M. A., On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types, BMC Bioinformatics, 15, 1, 110 (2014) |
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.
