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_i{X}_j=X_j{X}_i$, and (iv) $X_1{X}_1^T+X_2{X}_2^T+X_3{X}_3^T+X_4{X}_4^T=4n{I}_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\le 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\le 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\$-matricestoconstructsome\text{(}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 \emph{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 $(\frac{1}{\sqrt{2}}+o(1))\sqrt{n\log n}$ as $n\to \mathrm{\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 $(\frac{3}{\sqrt{2}}+o(1))\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 $(\frac{1}{2\sqrt{2}}+o(1))\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].

As an extension of the fractional domination and fractional domatic graphical parameters, multi-fractional domination parameters are introduced. We demonstrate the Linear Programming formulations, and to these formulations we apply the Partition Class Theorem, which is a generalization of the Automorphism Class Theorem. We investigate some properties of the multi-fractional domination numbers and their relationships to the fractional domination and fractional domatic numbers.

In a graph, the Steiner distance of a set of vertices $U$ is the minimum number of edges in a connected subgraph containing $U$. For $k\ge 2$ and $d\ge k-1$, let $S(k,d)$ denote the property that for all sets $S$ of $k$ vertices with Steiner distance $d$, the Steiner distance of $S$ is preserved in any induced connected subgraph containing $S$. A $k$-Steiner-distance-hereditary ($k$-SDH) graph is one with the property $S(k,d)$ for all $d$. We show that property $S(k,k)$ is equivalent to being $k$-SDH, and that being $k$-SDH implies $(k+1)$-SDH. This establishes a conjecture of Day, Oellermann and Swart.

The quantity $g^{(k)}(v)$ was introduced in [4] as the minimum number of blocks necessary in a pairwise balanced design on $v$ elements, subject to the condition that the longest block have cardinality $k$. When $k\ge (v–1)/2$, it is known that $g^{(k)}(v)=1+(v–k)(3k–v+1)/2$, except for the case when $v\equiv 1(\mathrm{mod}4)$ and $k=(v–1)/2$. This exceptional “case of first failure” was treated in [1] and [2]. In this paper, we discuss the structure of the “case of first failure” for the situation when $v=4s+4$.

We construct some codes, designs and graphs that have the first or second Janko group, $J_1$ or $J_2$, respectively, acting as an automorphism group. We show computationally that the full automorphism group of the design or graph in each case is $J_1$, $J_2$ or ${\overline{J}}_2$, the extension of $J_2$ by its outer automorphism, and we show that for some of the codes the same is true.

A 3-regular graph $G$ is called a 3-circulant if its adjacency matrix $A(G)$ is a circulant matrix. We show how all disconnected 3-circulants are made up of connected 3-circulants and classify all connected 3-circulants as one of two basic types. The rank of $A(G)$ is then completely determined for all 3-circulant graphs $G$.

The independence number ${\beta }_n$, for knights on equilateral triangular boards $T_n$, of regular hexagons is determined for all $n$.

It was conjectured by Lee that a cubic simple graph with $4k+2$ vertices is edge-magic [5]. In this paper we show that the conjecture is not true for multigraphs or disconnected simple graphs in general. Several new classes of cubic edge-magic graphs are exhibited.

In 1976 Erdős asked about the existence of Steiner triple systems that lack collections of $j$ blocks employing just $j+2$ points. This has led to the study of anti-Pasch, anti-mitre and 5-sparse Steiner triple systems. Simultaneously generating sets and bases for Steiner triple systems and $t$-designs have been determined. Combining these ideas, together with the observation that a regular graph is a 1-design, we arrive at a natural definition for the girth of a design. In turn, this provides a natural extension of the search for cages to the universe of all $t$-designs. We include the results of computational experiments that give an abundance of examples of these new definitions.

A graph $G$ is called an $L_1$-graph if, for each triple of vertices $x,y,\$and\text{(}z$ with $d(x,y)=2$ and $z\in N(x)\cap N(y)$, $d(x)+d(y)\ge |N(x)\cup N(y)\cup N(z)|–1$. Let $G$ be a $3$-connected $L_1$-graph of order $n\ge 18$. If $\delta (G)\ge n/3$, then every pair of vertices $u$ and $v$ in $G$ with $d(u,v)\ge 3$ is connected by a Hamiltonian path of $G$.

How many vertices must we delete from a graph so that it no longer contains a path $P_k$ on $k$ vertices? We explore this question for various special graphs (hypercubes, square lattice graphs) as well as for some general families.

A complete list is given of all finite trivalent arc-transitive connected graphs on up to 768 vertices, completing and extending the Foster census. Several previously undiscovered graphs appear, including one on 448 vertices which is the smallest arc-transitive trivalent graph having no automorphism of order 2 which reverses an arc. The graphs on the list are classified according to type (as described by Djokovic and Miller in terms of group amalgams), and were produced with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group. Further properties of each graph are also given: its girth, diameter, Hamiltonicity, and whether or not it is bipartite.

In this paper the decomposition of Dyck words into a product of Dyck prime subwords is studied. The set of Dyck words which are decomposed into $k$ components is constructed and its cardinal number is evaluated.

For an ordered set $W=\{w_1,w_2,\dots ,w_k\}$ of vertices and a vertex $v$ in a graph $G$, the representation of $v$ with respect to $W\$isthe\text{(}k$-vector $r(v|W)=(d(v,w_1),d(v,w_2),\dots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations. A resolving set containing a minimum number of vertices is called a basis for $G$ and the number of vertices in a basis is the (metric) dimension $\dim G$. A connected graph is unicyclic if it contains exactly one cycle. For a unicyclic graph $G$, tight bounds for $\dim G$ are derived. It is shown that all numbers between these bounds are attainable as the dimension of some unicyclic graph.

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of the extremal problems. We define a $(p,q,\kappa ,\delta )$ graph as a graph having $p$ vertices, $q$ edges, vertex connectivity $\kappa$ and minimum degree $\delta$. An arbitrary quadruple of integers $(a,b,c,d)$ is called $(p,q,\kappa ,\delta )$ realizable if there is a $(p,q,\kappa ,\delta )$ graph with $p=a,q=b,\kappa =c\$and\text{(}\delta =d$. Necessary and sufficient conditions for a quadruple to be $(p,q,\kappa ,\delta )$ realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for $(p,q,\kappa ),(p,q,\lambda ),(p,4,\delta ),(p,\mathrm{\Delta },\delta ,\lambda )$ and $(p,\mathrm{\Delta },\delta ,\kappa )$ realizability, where $\mathrm{\Delta }$ denotes the maximum degree for all vertices in a graph and $\lambda$ denotes the edge connectivity of a graph.