Clique partitions of glued graphs

Abstract

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 as the original graphs. A clique partition of a graph is a set of its cliques which together contain each edge exactly once. The clique partition number of a graph is the smallest cardinality of its clique partitions. We study bounds of clique partition numbers of glued graphs in terms of clique partition numbers of their original graphs. Also, we investigate values or bounds of clique partition numbers of clique-preserving glued graphs and glued graphs with specified clones such as complete graphs K2 and K3.