On the termination of some biclique operators on multipartite graphs - Sorbonne Université
Article Dans Une Revue Discrete Applied Mathematics Année : 2015

On the termination of some biclique operators on multipartite graphs

Résumé

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.
Fichier principal
Vignette du fichier
Multipartie.pdf (459.54 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01200865 , version 1 (17-09-2015)

Identifiants

Citer

Christophe Crespelle, Matthieu Latapy, Thi Ha Duong Phan. On the termination of some biclique operators on multipartite graphs. Discrete Applied Mathematics, 2015, 195, pp.59-73. ⟨10.1016/j.dam.2015.02.006⟩. ⟨hal-01200865⟩
382 Consultations
173 Téléchargements

Altmetric

Partager

More