On the termination of some biclique operators on multipartite graphs. (English) Zbl 1320.05117
Summary: We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C38 | Paths and cycles |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
Software:
LCMReferences:
| [1] | Albert, R.; Barabási, A. L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 47 (2002) · Zbl 1205.82086 |
| [2] | Alexe, G.; Alexe, S.; Crama, Y.; Foldes, S.; Hammer, P. L.; Simeone, B., Consensus algorithms for the generation of all maximal bicliques, Discrete Appl. Math., 145, 11-21 (2004) · Zbl 1056.05132 |
| [4] | Barrat, A.; Barthélemy, M.; Vespignani, A., (Dynamical Processes on Complex Networks (2010), Cambridge University Press) |
| [5] | Bender, E. A.; Canfield, E., The asymptotic number of labeled graphs with given degree sequences, J. Combin. Theory Ser. A, 24, 296-307 (1978) · Zbl 0402.05042 |
| [6] | Bornstein, C. F.; Szwarcfiter, J. L., On clique convergent graphs, Graphs Combin., 11, 213-220 (1995) · Zbl 0841.05094 |
| [7] | Cerioli, M. R., Clique graphs and edge-clique graphs, Electron. Notes Discrete Math., 13, 34-37 (2003), 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization · Zbl 1075.05572 |
| [8] | Chartrand, G.; Kapoor, S. F.; McKee, T. A.; Saba, F., Edge-clique graphs, Graphs Combin., 7, 253-264 (1991) · Zbl 0756.05066 |
| [9] | Crespelle, C.; Phan, T. H.D.; Tran, T. H., Termination of the iterated strong-factor operator on multipartite graphs, Theoret. Comput. Sci., 571, 67-77 (2015) · Zbl 1306.05234 |
| [10] | Evans, T., Clique graphs and overlapping communities, J. Stat. Mech. Theory Exp., 2010, P12037 (2010) |
| [11] | Gély, A.; Nourine, L.; Sadi, B., Enumeration aspects of maximal cliques and bicliques, Discrete Appl. Math., 157, 1447-1459 (2009) · Zbl 1177.05056 |
| [12] | Groshaus, M.; Montero, L. P., The number of convergent graphs under the biclique operator with no twin vertices is finite, Electron. Notes Discrete Math., 35, 241-246 (2009) · Zbl 1268.05107 |
| [13] | Groshaus, M.; Montero, L. P., On the iterated biclique operator, J. Graph Theory, 73, 181-190 (2013) · Zbl 1262.05117 |
| [14] | Guillaume, J. L.; Latapy, M., Bipartite structure of all complex networks, Inform. Process. Lett., 90, 215-221 (2004) · Zbl 1178.68031 |
| [15] | Guillaume, J. L.; Latapy, M., Bipartite graphs as models of complex networks, Physica A, 371, 795-813 (2006) |
| [16] | Larrión, F.; de Mello, C. P.; Morgana, A.; Neumann-Lara, V.; Pizaña, M. A., The clique operator on cographs and serial graphs, Discrete Math., 282, 183-191 (2004) · Zbl 1042.05074 |
| [17] | Larrión, F.; Neumann-Lara, V.; Pizaña, M. A., Clique divergent clockwork graphs and partial orders, Discrete Appl. Math., 141, 195-207 (2004) · Zbl 1042.05072 |
| [18] | Larrión, F.; Pizaña, M. A.; Villarroel-Flores, R., Contractibility and the clique graph operator, Discrete Math., 308, 3461-3469 (2008) · Zbl 1171.05388 |
| [20] | Lin, M. C.; Soulignac, F. J.; Szwarcfiter, J. L., The clique operator on circular-arc graphs, Discrete Appl. Math., 158, 1259-1267 (2010) · Zbl 1209.05246 |
| [21] | Molloy, M.; Reed, B., A critical point for random graphs with a given degree sequence, Random Struct. Algorithms (1995) · Zbl 0823.05050 |
| [22] | Neumann-Lara, V., On clique-divergent graphs, Problèmes Combin. Théorie Graphes (Colloques internationaux du C.N.R.S., Paris), 260, 313-315 (1978) · Zbl 0413.05058 |
| [23] | Prisner, E., Convergence of iterated clique graphs, Discrete Math., 103, 199-207 (1992) · Zbl 0766.05096 |
| [24] | Szwarcfiter, J. L., A survey on clique graphs, (Borwein, J. M.; Borwein, P.; Reed, B. A.; Sales, C. L., Recent Advances in Algorithms and Combinatorics. Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics (2003), Springer: Springer New York), 109-136 · Zbl 1027.05071 |
| [25] | Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for generating all maximal cliques and computational experiments, Theoret. Comput. Sci., 363, 28-42 (2006) · Zbl 1153.68398 |
| [30] | Watts, D.; Strogatz, S., Collective dynamics of small-world networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
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.
