PARALLEL CRITICAL GRAPHS

PARALLEL CRITICAL GRAPHS

K. Karthika

[PDF]

Abstract

Let G1 and G2 be two undirected graphs. Let u1, v1 2 V ( G1 ) and u2, v2 2 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 su cient condition for parallel critical graphs. Few results relating to some class of graphs and parallel composition are discussed in this paper.

Keywords

Critical graph, domination number, graph operation, parallel composition graph, parallel critical graph.