Let \(H\) be a fixed graph without isolated vertices, and let \(G\) be a graph on \(n\) vertices. Let \(2 \leq k \leq n-1\) be an integer. We prove that if \(k \leq n-2\) and every \(k\)-vertex induced subgraph of \(G\) is \(H\)-decomposable, then \(G\) or its complement is either a complete graph or a complete bipartite graph. This also holds for \(k = n-1\) if all the degrees of the vertices of \(H\) have a common factor. On the other hand, we show that there are graphs \(H\) for which it is NP-Complete to decide if every \(n-1\)-vertex subgraph of \(G\) is \(H\)-decomposable. In particular, we show that \(H = K_{1,h-1}\), where \(h > 3\), are such graphs.

Let \(G\) be a finite group of order \(n \geq 2\), \((x_1, \ldots, x_{ n})\) an \(n\)-tuple of elements of \(G\) and \(A = (a_{ij})\) a square matrix of order \(n\) such that \(a_{ij} = x_ix_j\). We investigate how many different types of such matrices could exist for \(n = 2, 3\) and we deal with some of their properties. We show that for every group \(G\) the number of the ordered \(n\)-tuples corresponding to the same matrix is a multiple of \(|G|\).

The quantity \(g^k(v)\) was introduced in \([6]\) as the minimum number of blocks necessary in a pairwise balanced design on \(v\) elements, subject to the condition that the longest block has length \(k\). Recently, we have needed to use all possibilities for such minimal covering designs, and we record all non-isomorphic solutions to the problem for \(v \leq 13\).

For \(v \geq 3\), \(v\) odd, it is shown that there exists a decomposition of \(K_v\) into \(6\) cycles whose edges partition the edge set of \(K_v\), if and only if

\[\lfloor \frac{v-1}{2} \rfloor \leq b \lfloor \frac{v(v-1)}{6}\rfloor.\]
For even \(v\), \(v \geq 4\), a similar result is obtained for \(K_v\) minus a \(1\)-factor.

Upper bounds on \(K_q(n, R)\), the minimum number of codewords in a \(q\)-ary code of length \(n\) and covering radius \(R\), are improved. Such bounds are obtained by constructing corresponding covering codes. In particular, codes of length \(q+1\) are discussed. Good such codes can be obtained from maximum distance separable \((MDS)\) codes. Furthermore, they can often be combined effectively with other covering codes to obtain new ones. Most of the new codes are obtained by computer search using simulated annealing. The new results are collected in updated tables of upper bounds on \(K_q(n, R)\), \(q=3,4,5\).

The neighborhood or two-step graph, \(N(G)\), of a graph \(G\) is the intersection graph of the open neighborhoods of the vertices of \(G\), and \(L(G)\) is the line graph of \(G\). The class of graphs for which \(N[L(G)] \equiv L[N(G)]\) consists of those graphs for which every component is either \(K_1\), \(K_{1,3}\), or \(C_n\) where \(n \geq 3\) and \(n \neq 4\).

We consider several families of regular bipartite graphs, most of which are vertex-transitive, and investigate the problem of determining which ones are subgraphs of hypercubes. We define \(H_{k,r}\) as the graph on \(k\) vertices \(0,1,2,\ldots,k-1\) which form a \(k\)-cycle (when traversed in that order), with the additional edges \((i,i+r)\) for \(i\) even, where \(i+r\) is computed modulo \(k\). Since this graph contains both a \(k\)-cycle and an \((r+1)\)-cycle, it is bipartite (if and only if) \(k\) is even and \(r\) is odd. (For the “if” part, the bipartition \((X,Y)\) is given by \(X =\) even vertices and \(Y =\) odd vertices.) Thus we consider only the cases \(r = 3,5,7\). We find that \(H_{k,3}\) is a subgraph of a hypercube precisely when \(k \equiv 0 \pmod{4}\). \(H_{k,5}\) can be embedded in a hypercube precisely when \(k \equiv 0 \pmod{16}\). For \(r = 7\) we show that \(H_{k,7}\) is embeddable in a hypercube whenever \(k \equiv 0 \pmod{16}\).

A graph \(G\) is said to be embeddable in a set \(X\) if there exists a mapping \(f\) from \(E(G)\) to the set \(\mathcal{P}(X)\) of all subsets of \(X\) such that if we define a mapping \(g\) from \(V(G)\) to \(\mathcal{P}(X)\) by letting \(g(x)\) be the union of \(f(e)\) as \(e\) ranges over all edges incident with \(x\), then \(g\) is injective. We show that for each integer \(k \geq 2\), every graph of order at most \(2^k\) all of whose components have order at least \(3\) is embeddable in a set of cardinality \(k\).

Let \(D\) be a set of natural numbers. The distance graph \(G(D)\) has the integers as vertex set and two vertices \(u\) and \(v\) are adjacent if and only if \(|u – v| \in D\).
In the eighties, there have been some results concerning the chromatic number \(\chi(D)\) of these graphs, especially by Eggleton, Erdős, Skilton, and Walther. Most of these investigations are concentrated on distance graphs where the distance set \(D\) is a subset of primes.
This paper deals with the chromatic number of distance graphs of \(3\)-element distance sets without further restrictions for the elements of \(D\).