The essential cutset number and connectivity of the join and composition of graphs

Abstract

In a connected graph G a subset Y of V(G) is a cutset of G if the removal of Y from G yields a disconnected subgraph. If Y is a cutset of G such that Y cannot be reduced into a smaller cutset of G, then Y is called an essential cutset of G. The essential cutset number of G, denoted by ecs(G), is defined as the maximum cardinality of an essential cutset of G. In this paper, the essential cutsets of the join G + H and composition G[H] of two connected graphs G and H are characterized. From the resulting characterizations, the essential cutset numbers (as well as the vertex connectivity) of the aforementioned graphs are computed. The essential cutset numbers and connectivity of some known classes of graphs are also presented.