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.