On Edge-integrity Maximal Graphs

Abstract

The edge-integrity of a graph $G$ is given by
$$\underset{S\subseteq E(G)}{min}\{|S|+m(G–S)\},$$
where $m(G–S)$ denotes the maximum order of a component of $G–S$.
Let $I^{\prime }(G)$ denote the edge-integrity of a graph $G$. We define a graph $G$ to be $I^{\prime }$-maximal if for every edge $e$ in $\overline{G}$, the complement of graph $G$, $I^{\prime }(G+e)>I^{\prime }(G)$. In this paper, some basic results of $I^{\prime }$-maximal graphs are established, the girth of a connected $I^{\prime }$-maximal graph is given and lower and upper bounds on the size of $I^{\prime }$-maximal connected graphs with given order and edge-integrity are investigated. The $I^{\prime }$-maximal trees and unicyclic graphs are completely characterized.