Parallel critical graphs

Abstract

Let G1 and G2 be two undirected graphs. Let u1, v1 ? V ( G1 ) and u2, v2 ? V ( G2 ). A parallel composition forms a new graph H that combines G1 and G2 by contracting the vertices u1 with u2 and v1 with v2. A new kind of graph called a parallel critical graph is introduced in this paper. We present the critical property using the domination number of G1 and G2 and provide a necessary and sufficient condition for parallel critical graphs. Few results relating to some class of graphs and parallel composition are discussed in this paper.