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.

A graph \(G\) is istance-hereditary if for every connected induced subgraph \(H\) of \(G\) and every pair \(u,v\) of vertices of \(H\), we have \(d_H(u,v) = d_G(u,v)\). A frequently occurring communication problem in a multicomputer is to determine the most efficient way of routing a message from a processor (called the source) to a number of other processors (called the destinations). When devising a routing from a source to several destinations it is important that each destination receives the source message in a minimum number of time steps and that the total number of messages generated be minimized. Suppose \(G\) is the graph that models a multicomputer and let \(M = \{s, v_1, v_2, \ldots, v_k\}\) be a subset of \(V(G)\) such that \(s\) corresponds to the source node and the nodes \(v_1, v_2, \ldots, v_k\) correspond to the destinations nodes. Then an optimal communication tree (OCT) \(T\) for \(M\) is a tree that satisfies the following conditions:

1. \(M \subseteq V(T)\),
2. \(d_T(s, v_i) = d_G(s, v_i)\) for \(1 \leq i \leq k\),
3. no tree \(T’\) satisfying (a) and (b) has fewer vertices than \(T\).

It is known that the problem of finding an OCT is NP-hard for graphs \(G\) in general, and even in the case where \(G\) is the \(n\)-cube, or a graph whose maximum degree is at most three. In this article, it is shown that an OCT for a given set \(M\) in a distance-hereditary graph can be found in polynomial time. Moreover, the problem of finding the minimum number of edges in a distance-hereditary graph \(H\) that contains a given graph \(G\) as spanning subgraph is considered, where \(H\) is isomorphic to the \(n\)-cycle, the \(s\)-cube or the grid.

A graph is said to be \({well-covered}\) if all maximal independent sets of vertices in the graph have the same cardinality. Determining whether a graph is well-covered has recently been shown (independently by Chvátal and Slater and by Sankaranarayana and Stewart) to be a co-NP-complete problem. In this paper, we characterise all well-covered cubic (\(3\)-regular) graphs. Our characterisation yields a polynomial time algorithm for recognising well-covered cubic graphs.

It is proved in this paper that there exists a simple \(B[4 ,6; v]\) for every \(v \geq 6\). It is also proved that there exists an indecomposable simple \(B[4, 6; v]\) for every \(v \geq 6, v \notin \{12, 13, 16, 17, 20\}\).

An efficient algorithm for calculating the chromatic polynomial of large graphs relative to the tree basis is presented. As an application of this algorithm, the degree thirty-two chromatic polynomial of the dual of the truncated icosahedron is calculated. Before this algorithm, only the by-hand calculations of Hall, Siry, and Vander-slice, completed in 1965, had produced this chromatic polynomial.

Generalized difference sets are difference sets with prescribed (and possibly different) multiplicities for every element. In this paper, constructions will be given for generalized difference sets on the semigroup of positive integer for almost every possible multiplicity function (sequence of multiplicities).