THE BICLIQUE PARTITION NUMBER OF SOME IMPORTANT GRAPHS

Abstract

The biclique partition number of a graph G, bp(G) is the minimum number of complete bipartite subgraphs needed to partition the edge set of G.  Let r(G) = max{n₊(G), n₋(G)} where n₊(G), n₋(G) are the number of positive and the number of negative eigenvalues of the adjacency matrix of G, respectively.  A graph G satisfying, bp(G) = r(G) is called an eigensharp graph.  In this paper we apply Pollak and Graham Theorem to find the biclique partition number of the line graph of complete graph and its complement, the line graph of complete bipartite graph and its complement and the line graph of a tree graph and we discuss the eigensharp property of these graphs.  Also we identify the biclique partition number of the kth-power graph of paths and cycles.