Hub edge-integrity of graphs

Abstract

The hub-integrity of a graph is given by the minimum of $|S|+m(G–S)$, where $S$ is a hub set and $m(G–S)$ is the maximum order of the components of $G–S$. In this paper, the concept of hub edge-integrity is introduced as a new measure of the stability of a graph $G$, and it is defined as $HEI(G)=min\{|S|+m(G–S)\},$ where $S$ is an edge hub set and $m(G–S)$ is the order of a maximum component of $G–S$. Furthermore, an $HEI$-set of $G$ is any set $S$ for which this minimum is attained. Several properties and bounds on the $HEI$ are presented, and the relationship between $HEI$ and other parameters is investigated. The $HEI$ of some classes of graphs is also computed.