On the termination of some biclique operators on multipartite graphs - Sorbonne Université Access content directly
Journal Articles Discrete Applied Mathematics Year : 2015

On the termination of some biclique operators on multipartite graphs

Abstract

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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
333 View
149 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More