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.

The numbers of sets of independent edge sets in \(2\)-lattice graphs, wheel graphs, and circuit graphs are computed.

It is well-known that if \(D\) is any finite set of integers, then there is an \(n\) large enough so that there exists a 2-coloring of the positive integers that avoids any monochromatic \(n\)-term arithmetic progressions whose common differences belong to \(D\).If \(\vec{d} = (d_1, \ldots, d_k)\) and \(\vec{n} = (n_1, \ldots, n_k)\) are \(k\)-tuples of positive integers, denote by \(f_{\vec{d}}(\vec{n})\) the least positive integer \(N\), if it exists, such that for every 2-coloring of \([1, N]\) there is, for some \(i\), a monochromatic \(n_i\)-term arithmetic progression with common difference \(d_i\).This paper looks at the problem of determining when \(f_{\vec{d}}(\vec{n})\) exists, and its value when it does exist, for \(k \leq 3\).A complete answer is given for \(k = 2\).A partial answer is given for \(k = 3\), including the fact that for all ordered triples \(\vec{d}\), \(f_{\vec{d}}(4, 4, 4)\) does not exist.

Given a set of \(N\) cities, construct a connected network which has minimum length. The problem is simple enough, but the catch is that you are allowed to add junctions in your network. Therefore, the problem becomes how many extra junctions should be added, and where should they be placed so as to minimize the overall network length.This intriguing optimization problem is known as the Steiner Minimal Tree Problem (SMT), where the junctions that are added to the network are called Steiner Points.The focus of this paper is twofold.First We look at the computational history of the problem, up through and including a new method to compute SMT’s in parallel.Secondly We look at future work in the computation of Steiner Minimal Trees.