On the Integrity of Combinations of Graphs

Abstract

The integrity of a graph $G$, denoted $I(G)$, is defined by $I(G):=\underset{S\subset V(G)}{min}\{|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.