On cliques and bicliques

Basic definitions are given in the next paragraph. We study second clique graphs of suspensions of graphs, K 2 ( S ( G ) ) , and characterize them, in terms of an auxiliary biclique operator B which transforms a graph G into its biclique graph B(G). The characterization is then: K 2 ( S ( G ) ) ≅ B ( K ( G ) ) . We found a characterization of the graphs, G, that maximize | B ( G ) | for any given order n = | G | . This particular version of a biclique operator is new in the literature. The main motivation to study B(G) is an attempt to characterize the graphs G that maximize | K 2 ( G ) | , thus mimicking a result of Moon and Moser [12] that characterizes the graphs maximizing | K ( G ) | . The clique graph K(G) of a a graph G is the intersection graph of the set of all (maximal) cliques of G (and K 2 ( G ) = K ( K ( G ) ) ). The suspension S(G) of a graph G is the graph obtained from G by adding two new vertices which are adjacent to all other vertices, but not to each other. Here, a biclique (X, Y ) is an ordered pair of not necessarily disjoint subsets of vertices of G such that each x ∈ X is adjacent or equal to every y ∈ Y and such that (X, Y ) is maximal under component-wise inclusion. Finally B(G) is the graph whose vertices are the bicliques of G with adjacencies given by ( X , Y ) ≃ ( X ′ , Y ′ ) if and only if X ∩ X ′ ≠ ∅ or Y ∩ Y ′ ≠ ∅ .