The quantity \(B(G) = \min \max\{|f(u)-f(v)|: (u,v) \in E(G)\}\) is called the bandwidth of a graph \(G = (V(G), E(G))\) where \(\min\) is taken over all bijections \(f: V(G) \to \{1,2,\ldots,|V(G)|\}\) called labelings. L.H. Harper presented an important inequality related to the boundary of subsets \(S \subseteq V(G)\). This paper gives a refinement of Harper’s inequality which will be more powerful in determining bandwidths for several classes of graphs.

In this paper we consider the problem of constructing magic rectangles of size \(m \times n\) where \(m\) and \(n\) are nonprime integers. What seems to be two new methods of constructing such rectangles are given.

The point-distinguishing chromatic index \(\chi_o(G)\) of a graph \(G\) represents the minimum number of colours in an edge colouring of \(G\) such that each vertex of \(G\) is distinguished by the set of colours of its incident edges. It is known that \(\chi_o(K_{n,n})\) is a non-decreasing function of \(n\) with jumps of value \(1\). We prove that \(\chi_o(K_{46,46}) = 7\) and \(\chi_o(K_{47,47}) = 8\).

There have been many results concerning claw-free graphs and hamiltonicity. Recently, Jackson and Wormald have obtained more general results on walks in claw-free graphs. In this paper, we consider the family of almost claw-free graphs that contains the previous one, and give some results on walks, especially on shortest covering walks visiting only once some given vertices.

A \(t\)-(n, k, \(\lambda\)) covering design consists of a collection of \(k\)-element subsets (blocks) of an \(n\)-element set \(\chi\) such that each \(t\)-element subset of \(\chi\) occurs in at least \(\lambda\) blocks. We use probabilistic techniques to obtain a general upper bound for the minimum size of such designs, extending a result of Erdős and Spencer [4].

In this paper, difference sets in groups containing subgroups of index \(2\) are considered, especially groups of order \(2m\) where \(m\) is odd. The author shows that the only difference sets in groups of order \(2p^\alpha\) are trivial. The same conclusion is true for some special parameters.

We completely classify the graphs all of whose neighbourhoods of vertices are isomorphic to \(P^k_n\) (\(2 \leq k \leq n\)), where \(P^k_n\) is the \(k\)-th power of the path \(P_n\) of length \(n-1\).

Let \(G\) be a finite group and let \(p_i(G)\) denote the proportion of \((x,y) \in G^2\) for which the set \(\{x^2, xy, yx, y^2\}\) has cardinality \(i\). We show that either \(0 < p_1(G) + p_2(G) \leq \frac{1}{2}\) or \(p_1(G) + p_2(G) = 1\), and that either \(p_4(G) = 0\) or \(\frac{5}{32} \leq p_4(G) < 1\). Each of the preceding inequalities are the best possible.

Using linear algebra over \(\text{GF}(2)\) we supply simple proofs to three parity theorems: Gallai’s partition theorem, the odd-parity cover theorem of Sutner, and generalize the “odd-cycle property” theorem of Manber and Shao to binary matroids.