The quantity \(g_2^{(k)}(v)\) is the minimum number of blocks in a family of blocks from a \(v\)-set that covers all \(\binom{v}{2}\) pairs exactly twice, given the restriction that the longest block in the covering family has length \(k\) (there may be many blocks of length \(k\)). We give certain results for the case \(k = 4\).

A set of edges \(D\) in a graph \(G\) is a dominating set of edges if every edge not in \(D\) is adjacent to at least one edge in \(D\). The minimum cardinality of an edge dominating set of \(G\) is the edge domination number of \(G\), denoted \(D_E(G)\). A graph \(G\) is edge domination critical, or \(EDC\), if for any vertex \(v\) in \(G\) we have \(D_E(G – v) = D_E(G) – 1\). Every graph \(G\) must have an induced subgraph \(F\) such that \(F\) is \(EDC\) and \(D_E(G) = D_E(F)\). In this paper, we prove that no tree with more than 2 vertices is \(EDC\), develop a forbidden subgraph characterization for the edge domination number of a tree, and we develop a construction that conserves the \(EDC\) property.

Let \(V\) be a finite set of order \(v\). A \((v,k,\lambda)\) covering design of index \(\lambda\) and block size \(k\) is a collection of \(k\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks, \(\alpha(v, k, \lambda)\), in a covering design. It is well known that \(\alpha(v, k, \lambda) \geq \left\lceil\frac{v}{k} \lceil \frac{v-1}{k-1}.\lambda \rceil \right\rceil=\phi(v, k, \lambda)\), where \(\lceil x \rceil\) is the smallest integer satisfying \(x\leq\lceil x \rceil\). In this paper, we determine the value \(\alpha(v,5,\lambda)\), with few possible exceptions, for \(\lambda = 3\), \(v \equiv 2 \pmod{4}\) and \(\lambda = 9, 10, v\geq5\), and \(\lambda \geq 11\), \(v \equiv 2 \pmod{4}\).

Let \(G = (V, E)\) be a connected undirected graph. Suppose a fire breaks out at a vertex of \(G\) and spreads to all its unprotected neighbours in each time interval. Also, one vertex can be protected in each time interval. We are interested in the number of vertices that can be “saved”, that is, which will never be burned. An algorithm is presented to find the optimal solution in the 2-dimensional grid graphs and 3-dimensional cubic graphs. We also determined the upper and lower bounds of the maximum number of vertices that can be saved on the large product graphs. The problem of containing the fire with one firefighter or more is also considered.

Let \(C\) be the underlying graph of a configuration of \(l\) blocks in a path design of order \(v\) and block size \(3\), \((V, \mathcal{B})\). We say that \((V, \mathcal{B})\) is \((l,C)\)-ordered if it is possible to order its blocks in such a way that each set of \(l\) consecutive blocks has the same underlying graph \(C\). In this paper, we completely solve the problem of the existence of a \((2,C)\)-ordered path design \(P(v, 3, 1)\) for any configuration having two blocks.

Summary. In this paper, we present some inequalities on balanced arrays \((B-arrays)\) of strength five with two symbols.

A kite is a triangle with a tail consisting of a single edge. A kite system of order \(n\) is a pair \((X,K)\), where \(K\) is a collection of edge disjoint kites which partitions the edge set of \(K_n\) (= the complete undirected graph on \(n\) vertices) with vertex set \(X\). Let \((X,B)\) be a block design with block size 4. If we remove a path of length 2 from each block in \(B\), we obtain a partial kite-system. If the deleted edges can be assembled into kites the result is a kite system, called a \emph{metamorphosis} of the block design \((X,B)\). There is an obvious extension of this definition to \(\lambda\)-fold block designs with block size 4. In this paper we give a complete solution of the following problem: Determine all pairs \((\lambda, n)\) such that there exists a \(\lambda\)-fold block design of order \(n\) with block size 4 having a metamorphosis into a \(\lambda\)-fold kite system.

We introduce the concept of equal chromatic partition of networks. This concept is useful for deriving lower bounds and upper bounds for performance ratios of dynamic tree embedding schemes that arise in a wide range of tree-structured parallel computations. We provide necessary and sufficient conditions for the existence of equal chromatic partitions of several classes of interconnection networks which include \(X\)-Nets, folded hypercubes, \(X\)-trees, \(n\)-dimensional tori and \(k\)y \(n\)-cubes. We use the pyramid network as an example to show that some networks do not have equal chromatic partitions, but may have near-equal chromatic partitions.

Let \(X_1,X_2,X_3,X_4\) be four type 1 \((1,-1)\) matrices on the same group of order \(n\) (odd) with the properties: (i) \((X_i – I)^T = -(X_i – I)\), \(i=1,2\), (ii) \(X_i^T = X_i\), \(i = 3,4\) and the diagonal elements are positive, (iii) \(X_iX_j = X_jX_i\), and (iv) \(X_1X_1^T + X_2X_2^T + X_3X_3^T + X_4X_4^T = 4nI_n\). Call such matrices \(G\)-matrices. If there exist circulant \(G\)-matrices of order \(n\) it can be easily shown that \(4n – 2 = a^2 + b^2\), where \(a\) and \(b\) are odd integers. It is known that they exist for odd \(n \leq 27\), except for \(n = 11,17\) for which orders they can not exist. In this paper we give for the first time all non-equivalent circulant \(G\)-matrices of odd order \(n \leq 33\) as well as some new non-equivalent circulant \(G\)-matrices of order \(n = 37,41\). We note that no \(G\)-matrices were previously known for orders 31, 33, 37 and 41. These are presented in tables in the form of the corresponding non-equivalent supplementary difference sets. In the sequel we use \(G$-matrices to construct some \(F\)-matrices and orthogonal designs.

The clique graph \(K(G)\) of a given graph \(G\) is the intersection graph of the collection of maximal cliques of \(G\). Given a family \(\mathcal{F}\) of graphs, the \({clique-inverse \;graphs}\) of \(\mathcal{F}\) are the graphs whose clique graphs belong to \(\mathcal{F}\). In this work, we describe characterizations for clique-inverse graphs of bipartite graphs, chordal bipartite graphs, and trees. The characterizations lead to polynomial time algorithms for the corresponding recognition problems.