On Edge-integrity Maximal Graphs

Abstract

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