On the Integrity of Combinations of Graphs

The integrity of a graph \(G\), denoted \(I(G)\), is defined by \(I(G) := \min_{S \subset V(G)} \{|S| + m(G – S)\}\), where \(m(G – S)\) denotes the maximum order of a component of \(G – S\). In this paper, we explore the integrity of various combinations of graphs in terms of the integrity and other graphical parameters of the constituent graphs. Specifically, explicit formulae and/or bounds are derived for the integrity of the join, union, cartesian and lexicographic products of two graphs. Also, some results on the integrity of powers of graphs are given.