Clique coverings and clique partitions of the K-power of graphs - Tanawat Wichianpaisarn (Chulalongkorn University, 2007)
Let G be any graph. A clique covering of G is a set of cliques of G, which together contain each edge of G at least once. The smallest cardinality of clique coverings of G is called the clique covering number of G, and is denoted by cc(G). A clique partition of G is a set of cliques of G, which together contain each edge of G exactly once. The smallest cardinality of clique partitions of G is called the clique partition number of G, and is denoted by cp(G). The graph Gk is the k-power of a graph G if V (Gk ) = V (G) and there is an edge between vertices u and v in Gk if and only if there is a path of length at most k between u and v in G. We investigate values or bound of the clique covering numbers and the clique partition numbers of the k-power of paths, cycles, pyramids, ladders and grids.