A connected graph $G$ is unicentered if $G$ has exactly one central vertex. It is proved that for integers $r$ and $d$ with $1\le r<d\le 2r$, there exists a unicentered graph $G$ such that rad$(G)=r$ and diam$(G)=d$. Also, it is shown that for any two graphs $F$ and $G$ with rad$(F)=n\ge 4$ and a positive integer $d$ ($4\le d\le n$), there exists a connected graph $H$ with diam$(H)=d$ such that the periphery and the center of $H$ are isomorphic to $F$ and $G$, respectively.

In this paper we obtain some inequalities on the existence of balanced arrays ($B$-arrays) of strength four in terms of its parameter by using Minkowski’s inequality.

Let $q$ be a prime power, $F_{q^2}$ the finite field with $q^2$ elements, $U_n(F_{q^2})$ the finite unitary group of degree $n$ over $F_{q^2}$, and $U{V}_n(F_{q^2})$ the $n$-dimensional unitary geometry over $F_{q^2}$. It is proven that the subgroup consisting of the elements of $U_n(F_{q^2})$ which fix a given $(m,s)$-type subspace of $U{V}_n(F_{q^2})$, acts transitively on some subsets of subspaces of $U{V}_n(F_{q^2})$. This observation gives rise to a number of Partially Balanced Incomplete Block Designs (PBIBD’s).

There are two criteria for optimality of weighing designs. One, which has been widely studied, is that the determinant of $X{X}^T$ should be maximal, where $X$ is the weighing matrix. The other is that the trace of $(X{X}^T{)}^{-1}$ should be minimal. We examine the second criterion. It is shown that Hadamard matrices, when they exist, are optimal with regard to the second criterion, just as they are for the first one.

In 1988, Sarvate and Seberry introduced a new method of construction for the family of weighing matrices $W(n^2(n-1),n^2)$, where $n$ is a prime power. We generalize this result, replacing the condition on $n$ with the weaker assumption that a generalized Hadamard matrix $GH(n;G)$ exists with $|G|=n$, and give conditions under which an analogous construction works for $|G|<n$. We generalize a related construction for a $W(13,9)$, also given by Sarvate and Seberry, producing a whole new class. We build further on these ideas to construct several other classes of weighing matrices.

For an integer $\ell \ge 2$, the $\ell$-connectivity ($\ell$-edge-connectivity) of a graph $G$ of order $p$ is the minimum number of vertices (edges) that need to be deleted from $G$ to produce a disconnected graph with at least $\ell$ components or a graph with at most $\ell -1$ vertices. Let $G$ be a graph of order $p$ and $\ell$-connectivity ${\kappa }_{\ell }$. For each $k\in \{0,1,\dots ,{\kappa }_{\ell }\}$, let $s_k$ be the minimum $\ell$-edge-connectivity among all graphs obtained from $G$ by deleting $k$ vertices from $G$. Then $f_{\ell }=\{(0,s_0),\dots ,({\kappa }_{\ell },s_{{\kappa }_{\ell }})\}$ is the $\ell$-connectivity function of $G$. The $\ell$-connectivity functions of complete multipartite graphs and caterpillars are determined.

An infinite class of graphs is constructed to demonstrate that the difference between the independent domination number and the domination number of $3$-connected cubic graphs may be arbitrarily large.

The domination number $\gamma (G)$ and the total domination number ${\gamma }_t(G)$ of a graph are generalized to the $K_n$-domination number ${\gamma }_{k_n}(G)$ and the total $K_n$-domination number ${\gamma }_{K_n}^t(G)$ for $n\ge 2$, where $\gamma (G)={\gamma }_{K_2}(G)$ and ${\gamma }_t(G)={\gamma }_{K_2}^t(G)$. A nondecreasing sequence $a_2,a_3,\dots ,a_m$ of positive integers is said to be a $K_n$-domination (total $K_n$-domination, respectively) sequence if it can be realized as the sequence of generalized domination (total domination, respectively) numbers ${\gamma }_{K_2}(G),{\gamma }_{K_3}(G),\dots ,{\gamma }_{K_m}(G)$ (${\gamma }_{K_2}^t(G),{\gamma }_{K_3}^t(G),\dots ,{\gamma }_{K_m}^t(G)$, respectively) of some graph $G$. It is shown that every nondecreasing sequence $a_2,a_3,\dots ,a_m$ of positive integers is a $K_n$-domination sequence (total $K_n$-domination sequence, if $a_2\ge 2$, respectively). Further, the minimum order of a graph $G$ with $a_2,a_3,\dots ,a_m$ as a $K_n$-domination sequence is determined. $K_n$-connectivity is defined and for $a_2\ge 2$ we establish the existence of a $K_m$-connected graph with $a_2,a_3,\dots ,a_m$ as a $K_n$-domination sequence for every nondecreasing sequence $a_2,a_3,\dots ,a_m$ of positive integers.

We study the problem of scheduling parallel programs with conditional branching on parallel processors. The major problem in having conditional branching is the non-determinism since the direction of a branch may be unknown until the program is midway in execution. In this paper, we overcome the problem of non-determinism by proposing a probabilistic model that distinguishes between branch and precedence relations in parallel programs. We approach the problem of scheduling task graphs that contain branches by representing all possible execution instances of the program by a single deterministic task graph, called the representative task graph. The representative task graph can be scheduled using one of the scheduling techniques used for deterministic cases. We also show that a schedule for the representative task graph can be used to obtain schedules for all execution instances of the program.

We give a list of all graphs of maximum degree three and order at most sixteen which are critical with respect to the total chromatic number.

In this paper we give a partial answer to a query of Lindner conceming the quasigroups arising from $2$-perfect $6$-cycle systems.

Consider the paths ${\pi }_t(i_1),\dots ,{\pi }_t(i_k)$ from the root to the leaves $i_1,\dots ,i_k$ in a random binary tree $t$ with $n$ internal nodes, where all such trees are assumed equally likely and the leaves are enumerated from left to right. We investigate, for fixed $i_1,\dots ,i_k$ and $n$, the average size of ${\pi }_t(i_1)\cup \dots \cup {\pi }_t(i_k)$ resp. of ${\pi }_t(i_1)\cap \dots \cap {\pi }_t(i_k)$ (the latter corresponding to the average depth of the smallest subtree containing $i_1,\dots ,i_k$). By a rotation argument, both problems are reduced to the case $k=1$, for which a solution is known. Furthermore, formulas for the probability distributions of the depth of leaf $i$, the distance between leaf $i$ and $j$ and the length of ${\pi }_t(i)\cap {\pi }_t(j)$ are derived.

Chetwynd and Hilton made the following $edge-colouringconjecture$: if a simple graph $G$ satisfies $\mathrm{\Delta }(G)>\frac{1}{3}|V(G)|$, then $G$ is Class $2$ if and only if it contains an overfull subgraph $H$ with $\mathrm{\Delta }(H)=\mathrm{\Delta }(G)$. They also made the following $total-colouringconjecture$: if a simple graph $G$ satisfies $\mathrm{\Delta }(G)\ge \frac{1}{2}(|V(G)|+1)$, then $G$ is Type $2$ if and only if $G$ contains a non-conformable subgraph $H$ with $\mathrm{\Delta }(H)=\mathrm{\Delta }(G)$. Here we show that if the edge-colouring conjecture is true for graphs of even order satisfying $\mathrm{\Delta }(G)>\frac{1}{2}|V(G)|$, then the total-colouring conjecture is true for graphs of odd order satisfying $\delta (G)\ge \frac{3}{4}|V(G)|–\frac{1}{4}$ and $\text{def}(G)\ge 2(\mathrm{\Delta }(G)–\delta (G)+1)$.

We correct an omission by Mathon in his classification of symmetric $(31,10,3)$-designs with a non-trivial automorphism group and find that there are a further six such designs, all with an automorphism group of order $3$.

A $dominatingfunction$ is a feasible solution to the LP relaxation of the minimum dominating set $0-1$ integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree $T$ can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in $T$, if one exists.

Let $H$ be a digraph whose vertices are called colours. Informally, an $H$-colouring of a digraph $G$ is an assignment of these colours to the vertices of $G$ so that adjacent vertices receive adjacent colours. In this paper we continue the study of the $H$-colouring problem, that is, the decision problem “Does there exist an $H$-colouring of a given digraph $G$?”. In particular, we prove that the $H$-colouring problem is NP-complete if the digraph $H$ consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as $H$ does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete $H$-colouring problems.

Bondy conjectures that if $G$ is a $2$-edge-connected simple graph with $n$ vertices, then at most $(2n-1)/3$ cycles in $G$ will cover $G$. In this note, we show that if $G$ is a plane triangulation with $n\ge 6$ vertices, then at most $(2n-3)/3$ cycles in $G$ will cover $G$.