Enumeration aspects of maximal cliques and bicliques

We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph GG, we introduce the notion of the transition graph T(G)T(G) whose vertices are maximal cliques of GG and arcs are transitions between cliques. We show that T(G)T(G) is a strongly connected graph and characterize a rooted cover tree of T(G)T(G) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119–123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505–517]. When GG is a bipartite graph, we show that the Galois lattice of GG is a partial graph of T(G)T(G) and we deduce that algorithms based on the Galois lattice are a particular search of T(G)T(G). Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 11–21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199–204] generate maximal bicliques of a bipartite graph in O(n2)O(n2) per maximal biclique, where nn is the number of vertices in GG. Finally, we show that under some specific numbering, the transition graph T(G)T(G) has a hamiltonian path for chordal and comparability graphs.