We define the class of \({hereditary \; clique-Helly \; graphs}\) or HCH \({graphs}\). It consists of those graphs, where the cliques of every induced subgraph obey the so-called `Helly-property’, namely, the total intersection of every family of pairwise intersecting cliques is nonempty. Several characterization and an \(O(|V|^2|E|)\) recognition algorithm for HCH graphs \(G = (V, E)\) are given. It is shown that the clique graph of every HCH graph is a HCH graph, and that conversely every HCH graph is the clique graph of some HCH graph. Finally, it is shown that HCH graphs \(G = (V, E)\) have at most \(|E|\) cliques, whence a maximum cardinality clique can be found in time \(O(|V||E|^2)\) in such a HCH graph.

A weight \(w: E(G) \rightarrow \{1, 2\}\) is called a \((1, 2)\)-eulerian weight of graph \(G\) if the total weight of each edge-cut is even. A \((1, 2)\)-eulerian weight \(w\) of \(G\) is called smallest if the total weight \(w\) of \(G\) is minimum. In this note, we prove that if graph \(G\) is \(2\)-connected and simple, and \(w_0\) is a smallest \((1, 2)\)-eulerian weight, then either \(|E_{w_0 = \text{even}}|\leq|V(G)| – 3\) or \(G = K_4\).

In this paper we prove that a \((v, u; \{4\}, 3)\)-IPBD exists when \(v, u \equiv 2\) or \(3 \pmod{4}\) and \(v \geq 3u + 1\), and then solve the problem of the existence of \((v, u; \{4\}, \lambda)\)-IPBD completely, which generalizes the result of \([7]\).

For a wide range of \(p\), we show that almost every graph \(G\epsilon\mathcal{G}(n,p)\) has no perfect dominating set and for almost every graph \(G\epsilon\mathcal{G}(n,p)\) we bound the cardinality of a set of vertices which can be perfectly dominated. We also show that almost every tree \(T\epsilon\mathcal{T}(n)\) has no perfect dominating set.

Necessary conditions for the existence of group divisible designs with block size three are developed. A computation is described that establishes the sufficiency of these conditions for sixty and fewer elements.

Four \(\{\pm1\}\)-matrices \(A, B, C, D\) of order \(n\) are called good matrices if \(A – I_n\) is skew-symmetric, \(B, C\), and \(D\) are symmetric, \(AA^T + BB^T + CC^T + DD^T = 4nI_n\), and, pairwise, they satisfy \(XY^T = YX^T\). It is known that they exist for odd \(n \leq 31\). We construct four sets of good matrices of order \(33\) and one set for each of the orders \(35\) and \(127\).

Consequently, there exist \(4\)-Williamson type matrices of order \(35\), and a complex Hadamard matrix of order \(70\). Such matrices are constructed here for the first time. We also deduce that there exists a Hadamard matrix of order \(1524\) with maximal excess.

For a nonempty subset \(S\) of vertices of a \(k\)-connected graph \(G\) and for \(1 \leq i \leq k\), the Steiner \(i\)-distance \(d_i(S)\) of \(S\) is the minimum size among all \(i\)-connected subgraphs containing \(S\). Relationships between Steiner \(i\)-distance and the connectivity and hamiltonian properties of a graph are discussed. For a \(k\)-connected graph \(G\) of order \(p\) and integers \(i\) and \(n\) with \(1 \leq i \leq k\) and \(1 \leq n \leq p\), the \((i, n)\)-eccentricity of a vertex \(v\) of \(G\) is the maximum Steiner \(i\)-distance \(d_i(S)\) of a set \(S\) containing \(v\) with \(|S| = n\). The \((i, n)\)-center \(C_{i,n}(G)\) of \(G\) is the subgraph induced by those vertices with minimum \((i, n)\)-eccentricity. It is proved that for every graph \(H\) and integers \(i,n \geq 2\), there exists an \(i\)-connected graph \(G\) such that \(C_{i,n}(G) \cong H\).

This paper studies the problem of allocating interacting program modules, of a distributed program, to the heterogeneous processors in a distributed computer system. The interacting program/task modules are represented by an undirected task graph, whose vertices denote task modules and edges denote interactions between modules. We are given the execution cost of a task module on each processor, the communication cost between two task modules if they are placed on different processors, and the interference cost between two task modules if they are placed on the same processor. The objective of our problem is to assign task modules to the processors such that the total of the above three costs incurred by the program on the system is minimized. The above task assignment problem is known to be NP-hard for a three processor system, but its complexity for a two processor system remained open. In this paper we prove that the problem remains NP-hard for a two processor system even when (1) task graph is planar and has maximum degree \(3\) or (2) task graph is bipartite. We then present three heuristics, based on simulated annealing, tabu search, and stochastic probe approaches respectively. We present an experimental analysis of these three heuristics, and compare their performance with the only known heuristic method in the literature. Our experiments demonstrate that our heuristics provide major improvements.

Let \(C(n, p)\) denote the set of all subsets of \(\{1, 2, \ldots, n\}\) whose sum is \(p\), and let \(C(n, k, p)\) denote the \(k\)-element sets of \(C(n, p)\). We show that the elements of \(C(n, p)\) and \(C(n, k, p)\) can be generated efficiently by simple recursive algorithms. The subsets are represented by characteristic bitstrings and by lists of elements. These representations can be generated in time that is proportional to the number of subsets generated.

Consider the problem of computing a stabber for polygonal objects. Given a set of objects \({S}\), an object that intersects with all of them is called the stabber of \({S}\). Polynomial time algorithms for constructing a line segment stabber for polygonal objects, if one exists, have been reported in the literature. We introduce the problem of stabbing polygonal objects by monotone chains. We show that a monotone chain that stabs the maximum number of given obstacles can be computed in \(O(n^2 \log n)\) time. We also prove that the maximum number of monotone chains required to stab all polygons can be computed in \(O(n^{2.5})\) time. The main tool used in developing both results is the construction of a directed acyclic graph induced by polygonal objects in a given direction. These results have applications for planning collision-free disjoint paths for several mobile robots in a manufacturing environment.

A secret sharing scheme protects a secret (key) by distributing related information among a group of participants. This is done in such a way that only certain pre-specified groups of these participants (the access structure) can reconstruct the secret. In this paper, we introduce a new measure of the efficiency of a perfect secret sharing scheme and examine methods of producing new secret sharing schemes from existing ones. These constructions can be used to help determine the optimal information rates for certain access structures.

In this paper, we prove that \(3\)-connected projective graphs with minimum valency \(5\) are edge reconstructible.

A set of blocks which is a subset of a unique \(t\)-\((v,k,\lambda_t)\) design is called a \({defining \; set}\) of that design. Using known results, an algorithm for finding smallest defining sets of any \(t\)-\((v,k,\lambda_t)\) design is described. Then the results of this algorithm as applied to the two \(2\)-\((13,3,1)\) designs are given.

The support of a \(t\)-design is the set of all distinct blocks of the design. The support size of a design is denoted by \(b^*\). In this paper, except for \(b^* = 23\), we completely determine the spectrum of support sizes of the case \(v = 10\), \(k = 5\), and \(t = 2\).

The problem of task allocation in distributed systems has been studied by many researchers. Several approaches have been used to model and study the problem, including integer programming, heuristic methods, and graph theoretic models. These approaches considered only restricted forms of the general problem. In this paper, we introduce a new model to represent the problem of allocating tasks on heterogeneous distributed systems. The model consists of a complete split graph that represents the communication cost among tasks as well as the execution cost of each task on the system processors. This model allows the incorporation of various constraints into the allocation problem. We show that the task allocation problem is equivalent to the problem of weighted clique partitioning in complete split graphs, which we proved to be NP-complete. We present a clique partitioning algorithm that employs the properties of split graphs for solving the problem in its general form. We show that the algorithm generates optimal solutions in some cases, while performing fairly well in general.

This paper discusses new Erdös-Gallai type necessary conditions for a sequence \(\prod\) of integers to be \(3\)-hypergraphic. Further, we show that some of the known necessary conditions for \(3\)-hypergraphic sequences are not sufficient.

It has been conjectured by D. R. Stinson that an incomplete Room square \((n, s)\)-IRS exists if and only if \(n\) and \(s\) are both odd and \(n \geq 3s + 2\), except for the nonexistent case \((n, s) = (5, 1)\). In this paper we shall improve the known results and show that the conjecture is true except for \(45\) pairs \((n, s)\) for which the existence of an \((n, s)\)-IRS remains undecided.