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.

Suppose \(S\) is a defining set of a symmetric \(2\)-( \(v, k, \lambda\) ) design \(D\), where \(\lambda = 1\) or \(2\); that is, \(D\) is a projective plane or a biplane.
In this paper, conditions under which the residual of \(S\) is a defining set of the residual of \(D\) are investigated.
As a consequence, inequalities relating the sizes of smallest defining sets of \(D\) and of the residual of \(D\) are obtained.
The exact sizes of smallest defining sets of \({PG}(2, 5)\), \({AG}(2, 5)\), and the three non-isomorphic \(2\)-( \(10, 4, 2\) ) designs are determined.

Exact designs with \(n\) observations and \(k\) two-level factors in the presence of autocorrelated errors are considered. The problem of finding \(D\)- and \(A\)- optimal designs is discussed. An algorithm for constructing such designs, using exhaustive search for different values of \(n\) and \(k\), is developed. The application of this algorithm showed that, in the case of positive autocorrelation, the maximum possible number of interchanges of the factor levels provides almost optimal designs.
On the contrary, in the case of negative autocorrelation, the minimum such number provides almost optimal designs. A list of the exact \(D\)- and \(A\)-optimal designs is given.

A tree \(T\) consisting of a line with edges \(\{(1, 2), (2, 3), \ldots, (n-1, n)\}\) and with edges \(\{(1, a_1), (1, a_2), \ldots, (1, a_k)\}\) (a star) attached on the left, is called a broom.
The edges of the tree \(T\) are called \(T\)-transpositions. We give an algorithm to factor any permutation \(\sigma\) of \(\{a_1, a_2, \ldots, a_k, 1, 2, \ldots ,n\}\) as a product of \(T\)-transpositions, and prove that the factorization produced by the algorithm has minimal length.

Median graphs are surveyed from the point of view of their characterizations, their role in location theory, and their connections with median structures. The median structures we present include ternary algebras, betweenness, interval structures, semilattices, hypergraphs, join geometries, and conflict models. In addition, some new characterizations of median graphs as meshed graphs are presented and a new characterization in terms of location theory is given.

Up to isomorphisms, there are exactly 22 \(1\)-rotational resolved \((52,4,1)\)-BIBD’s.

Let \(\mathcal{F}\) be a family of objects and \(\varphi\) an integer-valued function defined on \(\mathcal{F}\).
If for any \(A, B \in \mathcal{F}\) and integer \(k\) between \(\varphi(A)\) and \(\varphi(B)\), there exists \(C \in \mathcal{F}\) such that \(\varphi(C) = k\), then \(\varphi\) is said to interpolate over \(\mathcal{F}\).
In this paper, we first discuss some basic ideas used in proving interpolation theorems for graphs.
By using this, we then prove that a number of conditional invariants interpolate over some families of subgraphs of a given connected graph.

Scheduling graphs are used by algorithms such as PERT/CPM in order to determine an optimal schedule for a given project. It is well-known that dummy tasks (requiring zero processing time) must sometimes be incorporated into a scheduling graph.

The main tool in this paper is a new algorithm, RESOLVE, which creates a scheduling graph, typically with fewer dummy tasks than are produced by Richards’ algorithm (1967). A theoretical framework for scheduling graphs is systematically developed through several theorems, culminating in a demonstration of the validity of RESOLVE. A worked example illustrating the application of RESOLVE concludes the paper.

Let \(\mathcal{A} = \{A_1, \ldots, A_l\}\) be a partition of \([n]\) and \(\mathcal{F} = \{S_1, \ldots, S_m\}\) be an intersecting family of distinct nonempty subsets of \([n]\) such that \(\mathcal{A}\) and \(\mathcal{F}\) are pairwise intersecting families.Then
\[
|\mathcal{F}| \leq \frac{1}{2} \prod_{i=1}^{l} \left( 2^{|A_i|} – 2 \right) + \sum_{S\subsetneqq[l]} \left(\prod_{i\in S}\left( 2^{|A_i|} – 2 \right)\right).
\]
From this result and some properties of intersection graphs on multifamilies, we determine the intersection numbers of \(3\), \(4\), and \(5\)-regular graphs and some special graphs.

The concept of tenacity of a graph \(G\) was introduced in References [5,6] as a useful measure of the “vulnerability” of \(G\). In assessing the “vulnerability” of a graph, one determines the extent to which the graph retains certain properties after the removal of vertices or edges. In this paper, we will compare different measures of vulnerability with tenacity for several classes of graphs.

Particular balanced bipartite subgraph problems have applications in fields such as VLSI design and flexible manufacturing. An example of such problems is the following: given a graph \(G\) and a positive integer \(m\), does \(G\) contain a balanced complete bipartite subgraph with at least \(2m\) vertices? This problem is NP-complete for several classes of graphs, including bipartite graphs. However, the problem can be solved in polynomial time for particular graph classes. We aim to contribute to the characterization of “easy” classes of instances of the problem, and to individuate graph-theoretic properties that can be useful to develop solution algorithms for the general case. A simple polynomial algorithm can be devised for bipartite graphs with no induced \(P_5\) on the basis of a result of Bacsó and Tuza.
We generalize the result to particular subclasses of

1. graphs with no odd cycles of given size,
2. paw-free graphs,
3. diamond-free graphs.

Using computer algorithms, we show that in any \(2-(22, 8, 4)\) design, there are no blocks of type \(3\), thus leaving as possible only types \(1\) and \(2\).
Blocks of type \(3\), i.e., those which intersect two others in one point, are eliminated using the algorithms described in our previous paper. It was perhaps the second largest computation ever performed (after the solution to the RSA-129 challenge), requiring more than a century of cpu time.