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.

We prove that the domination number of every graph of diameter 2 on \(n\) vertices is at most \(\left(\frac{1}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\) as \(n \to \infty\) (with logarithm of base \(e\)). This result is applied to prove that if a graph of order \(n\) has diameter 2, then it contains a spanning caterpillar whose diameter does not exceed \(\left(\frac{3}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). These estimates are tight apart from a multiplicative constant, since there exist graphs of order \(n\) and diameter 2, with domination number not smaller than \(\left(\frac{1}{2\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). In contrast, in graphs of diameter 3, the domination number can be as large as \(\lfloor \frac{n}{2} \rfloor\) (but not larger).

Our results concerning diameter 2 improve the previous upper bound of \(O(n^{3/4})\), published by Faudree et al. in [Discuss. Math. Graph Theory 15 (1995), 111-118].