Menu
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
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.
