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.

A transitive orientation of a partial triple system \((S,T)\) of index \(2\lambda\) is a partial transitive triple system formed by replacing each triple \(t \in T\) with a transitive triple defined on the same vertex set as \(t\), such that each ordered pair occurs in at most \(\lambda\) of the resulting transitive triples. A transitive orientation \((S_1,T_1)\) of \((S,T)\) is said to be balanced if for all \(\{u,v\} \subseteq S\), if \(\{u,v\}\) occurs in \(\ell\) triples in \(T\) then \(\left\lfloor{\ell}/{2}\right\rfloor\)
and \(\left\lceil{\ell}/{2}\right\rceil\) transitive triples in \(T_1\) contain the arcs \((u,v)\) and \((v,u)\) respectively. In this paper, it is shown that every partial triple
system has a balanced transitive orientation. This result is then used to prove the existence of certain transitive group divisible designs.

The Prime Power Conjecture (PPC) states that abelian planar difference sets of order \(n\) exist only for \(n\) a prime power. Lander et al. have shown that orders divisible by certain composites can be eliminated. In this paper, we show how to extend this list of excluded orders.

A critical set \(C\) in a Latin square \(L\) is a partial Latin square which has a unique completion to \(L\) and for which no subset of \(C\) has this property. In this paper, I document known results on the possible sizes of critical sets, and provide a reference list for the existence of critical sets in Latin squares of order less than or equal to \(10\).Many of the results in this list are new, and where this is the case, I exhibit a critical set of the given size in the Appendix.

Let \(S^n\) be the \(n\)-dimensional sphere and \(K\) be the simplicial complex consisting of all faces of some \((n+1)\)-dimensional simplex. We present an explicit construction of a function \(g: S^n \to |K|\) such that for every \(x \in S^n\), the supports of \(g(x)\) and \(g(-x)\) are disjoint. This construction provides a new proof of the following result of Bajméczy and Bérdny \([1]\), which is a generalization of a theorem of Radon \([4]\):If \(f: |K| \to \mathbb{R}^n\) is a continuous map, then there are two disjoint faces \(\Delta_1, \Delta_2\) of \(\Delta\) such that \(f(\Delta_1) \cap f(\Delta_2) \neq \emptyset\).