Clique coverings of glued graphs

Abstract

Let G be a graph. A clique covering of a graph G is a set of cliques of G in which each edge of G is contained in at least one clique. The clique covering number of G is the smallest cardinality of clique coverings of G. A glued graph results from combining two vertex-disjoint graphs by identifying nontrivial connected isomorphic subgraphs of both graphs. Such subgraphs are referred to as the clones. The two vertex-disjoint graphs are referred to the original graphs. We study bounds of clique covering numbers of glued graphs in terms of clique covering numbers of their original graphs. Also, we investigate values or bounds of clique covering numbers of glued graphs with specified clones such as a complete graph, a complete graph and an induced subgraph of both original graphs.