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.