An upper bound on the size of any collection of mutually orthogonal partial Latin squares is derived as a function of the number of compatible cells that are occupied in all squares. It is shown that the bound is strict if the number of compatible cells is small.

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.

Let \(F\) and \(F’\) be two forests sharing the same vertex set \(V\) such that \(|E(F) \cap E(F’)| = \theta\). By \(F \cup F’\) we denote the graph on \(V\) with edge set \(E(F) \cup E(F’)\). Since both \(F\) and \(F’\) are \(2\)-colorable, we have \(\chi(F \cup F’) \leq 4\). In this paper we will investigate forests for which we can actually obtain this upper bound for the chromatic number. It will turn out that if neither \(F\) nor \(F’\) contain a path of length three then the chromatic number of \(F \cup F’\) is at most three. We will characterize those pairs of forests \(F\) and \(F’\) which both contain a path of length three and for which the chromatic number of \(F \cup F’\) is always at most three. In the case where one of the forests contains a path of length three and the other does not contain a path of length three we obtained only partial results. The problem then seems to be similar to a problem of Erdős which recently has been solved by Fleischner [2] using a theorem of Alon [3].

With Burnside’s lemma as the main tool, we derive a formula for the number of oriented triangle graphs and for the number of such graphs in which all largest cliques are transitively oriented.

This paper deals with \((a, d)\)-antimagic labelings of special graphs called parachutes. After the introduction of the concept of a parachute, the authors succeed in proving the finiteness of two very interesting subsets of the set of all \((a, d)\)-antimagic parachutes by means of a method using the theory of Diophantine equations and other number-theoretical results.

A rooted graph is a pair \((G, x)\), where \(G\) is a simple undirected graph and \(x \in V(G)\). If \(G\) is rooted at \(x\), its \(k\)-th rotation number \(h_k(G, x)\) is the minimum number of edges in a graph \(F\) of order \(|G| + k\) such that for every \(v \in V(F)\) we can find a copy of \(G\) in \(F\) with the root vertex \(x\) at \(v\); any such \(F\) of size \(h_k(G, x)\) is called a minimal graph. In this paper we prove that if \((G, x)\) is a rooted graph with \(d_{G}(x) = d\) then

\[p(G, x)=\lim_{k \to \infty} \frac{h_k(G, x)}{k} \]

exists and satisfies \(d/2 \leq p(G, x) \leq d\), where \(p(G, x)\) is termed the rotation index of \((G, x)\). We obtain the precise value of this parameter for several classes of rooted graphs and describe the asymptotic behaviour of corresponding minimal graphs.

A \(t\)-interval representation \(f\) of a graph \(G\) is a function which assigns to each vertex \(v \in V(G)\) a union of at most \(t\) closed intervals \(I_{v,1}, I_{v,2}, \ldots, I_{v,t}\) on the real line such that \(f(v) \cap f(w) \neq \emptyset\) if and only if \(v, w \in V(G)\) are adjacent. If no real number lies in more than \(r\) intervals of the representation, we say the interval representation has depth \(r\). The least positive integer \(t\) for which there exists a \(t\)-representation of depth \(r\) of \(G\) is called the depth-\(r\) interval number \(i_r(G)\). E. R. Scheinerman proved that \(i_2(K_n) = \lceil \frac{n}{2} \rceil\) for \(n \geq 2\) and that \(\lceil \frac{n-1}{2(r-1)}+\frac{r}{2n} \rceil \leq i_r(K_n) \leq \frac{n}{2r-2}+1+2\lceil log_r n \rceil \). In the following paper, we will see by construction that \(i_3(K_n) = \lceil \frac{n-1}{4}+\frac{3}{2n} \rceil \). If \(n \geq 5\), this is equal to \(\lceil \frac{n}{4} \rceil\). The main theorem is: if \(n \geq r \geq 4\), then \(i_r(K_n) \leq \max \{ \lceil \frac{n-2}{2(r-1)}+\frac{1}{2} \rceil , 2 \}\). The difference between the lower and upper bounds is at most \(1\).

Let \(L\) be a linear form on the Galois field \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\) (\(n \geq 2\)). We characterize those integers \(s\) coprime to \(v = (q^{n+1}-1)/(q-1)\) such that \(L(x^s)\) is (or is related to) a quadratic form on \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\). This relates to a conjecture of Games concerning quadrics of the form \(rD\) in \(\text{PG}(n,q)\), where \(D\) is a difference set in the cyclic group \({Z}_v\), acting as a Singer group on the points and hyperplanes of \(\text{PG}(n,q)\). It has been shown that Games’ conjecture does not hold except possibly in the case \(q = 2\): here we establish that it holds exactly when \(q = 2\). We also suggest a new conjecture. Our result for \(q=2\) enables us to prove another conjecture of Games’, concerning \(m\)-sequences with three-valued periodic cross-correlation function.

Let \(G\) be a group acting on a set \(\Omega\). A subset (finite or infinite) \(A \subseteq \Omega\) is called \(k\)-quasi-invariant, where \(k\) is a non-negative integer, if \(|A^g \backslash A| \leq k\) for every \(g \in G\). In previous work of the authors a bound was obtained, in terms of \(k\), on the size of the symmetric difference between a \(k\)-quasi-invariant subset and the \(G\)-invariant subset of \(\Omega\) closest to it. However, apart from the cases \(k = 0, 1\), this bound gave little information about the structure of a \(k\)-quasi-invariant subset. In this paper a classification of \(2\)-quasi-invariant subsets is given. Besides the generic examples (subsets of \(\Omega\) which have a symmetric difference of size at most \(2\) with some \(G\)-invariant subset) there are basically five explicitly determined possibilities.

This note is an extension of \([4]\) , wherein is shown a relation between the dual notions of graceful and edge-graceful graphs. In particular, this note proves two graceful conjectures raised in \([4]\) , and then utilizes the result to edge-gracefully label certain trees not previously known to be edge-graceful.

We present sufficient conditions for the existence of a \(k\)-factor in a simple graph depending on \(\sigma_2(G)\) and the neighbourhood of independent sets in our first theorem and on \(\sigma_2(G)\) and \(\alpha(G)\) in the second one.

It is well known that a necessary condition for the existence of a \((v, 4, 1)\)-RPMD is \(v \equiv 0 \text{ or } 1 \pmod{4}\) and the existence of \((v, 4, 1)\)-RPMDs for \(v \equiv 1 \pmod{4}\) has been completely settled.
In this paper, we shall introduce the concept of \((v, k, 1)\)-nearly-RPMDs and use it to obtain some new construction methods for \((v, k, 1)\)-RPMDs with \(v \equiv 0 \pmod{k}\). As an application, we shall show that a \((v, 4, 1)\)-RPMD exists for all integers \(v \geq 4\) where \(v \equiv 0 \pmod{4}\), except for \(v = 4, 8\) and with at most \(49\) possible exceptions of which the largest is \(336\).
It is also well known that a \((v, k, 1)\)-RPMD exists for all sufficiently large \(v\) with \(k \geq 3\) and \(v \equiv 1 \pmod{k}\), and a \((v, k, 1)\)-PMD exists with \(v(v – 1) \equiv 0 \pmod{k}\) for the case when \(k\) is an odd prime and \(v\) is sufficiently large. In this paper, we shall show that there exists a \((v, k, 1)\)-RPMD for all sufficiently large \(v\) with \(v \equiv 0 \pmod{k}\), and there exists a \((v, k,\lambda)\)-PMD for all sufficiently large \(v\) with \(\lambda v(v – 1) \equiv 0 \pmod{k}\).