We prove that the smallest covering code of length \(8\) and covering radius \(2\) has exactly \(12\) words. The proof is based on partial classification of even weight codewords, followed by a search for small sets of odd codewords covering the part of the space that has not been covered by the even subcode.

Alon and Yuster {[4]} have proven that if a fixed graph \(K\) on \(g\) vertices is \((h+1)\)-colorable, then any graph \(G\) with \(n\) vertices and minimum degree at least \(\frac{h}{h+1}n\) contains at least \((1-\epsilon)\frac{n}{g})\) vertex disjoint copies of \(K\), provided \(n>N(\epsilon)\). It is shown here that the required minimum degree of \(G\) for this result to follow is closer to \(\frac{h-1}{h }n\), provided \(K\) has a proper \((h+1)\)-coloring in which some of the colors occur rarely. A conjecture regarding the best possible result of this type is suggested.

Let \(G\) be a finite group with a normal subgroup \(H\). We prove that if there exist a \((h, r;\lambda, H)\) difference matrix and a \((g/h, r;1, G/H)\) difference matrix, then there exists a \((g, r;\lambda, G)\) difference matrix. This shows in particular that if there exist \(r\) mutually orthogonal orthomorphisms of \(H\) and \(r\) mutually orthogonal orthomorphisms of \(G/H\), then there exist \(r\) mutually orthogonal orthomorphisms of \(G\). We also show that a dihedral group of order \(16\) admits at least \(3\) mutually orthogonal orthomorphisms.

Let \(k\) and \(b\) be integers and \(k > 1\). A set \(S\) of integers is called \((k, b)\) linear-free (or \((k, b)\)-LF for short) if \(2 \in S\) implies \(kx + b \notin S\). Let \(F(n, k, b) = \max\{|A|: A \text{ is } (k, 0)\text{-LF and } A \subseteq [1, n]\}\), where \([1, n]\) denotes all integers between \(1\) and \(n\). A subset \(A\) of \([1, n]\) with \(|A| = F(n, k, b)\) is called a maximal \((k, b)\)-LF subset of \([1, n]\). In this paper, a recurrence relation for \(F(n, k, b)\) is obtained and a method to construct a maximal \((k, b)\)-LF subset of \([1, n]\) is given.

This paper deals with a new kind of graph labeling similar to the well known harmonious, graceful, and elegant labelings. A polychrome labeling of a simple and connected graph \(G = (V, E)\) by an abelian group \(A\) is a bijective map from \(V\) onto \(A\) such that the induced edge labeling \(f^*(uv) = f(v) + f(w), uv \in E\), is injective. Polychrome labelings of a path and a cycle by a large class of abelian groups are designed, and the connection to the above mentioned labelings is shown. In addition, the author presents a conjecture which is similar to a famous conjecture of G. Ringel about graceful trees (see {[9]}).

A graph is well-covered if it has no isolated vertices and all the maximal independent sets have the same cardinality. If furthermore this cardinality is exactly half the number of vertices, the graph is called very well covered. Sankaranarayana in \({[5]}\) presented a certain subclass of well covered graphs (called Wan) and gave a characterization of this class which generalized the characterization of very well covered graphs given by Favaron \([2]\) . The purpose of this article is to generalize to this new subclass some results concerning the stability, domination, and irredundance parameters proved for very well covered graphs in \([2]\) .

Three new characterizations of matroids are presented.

A decomposition of a graph \(H\) is a family of subgraphs of \(H\) such that each edge of \(H\) is contained in exactly one member of the family. For a graph \(G\), a \(G\)-decomposition of the graph \(H\) is a decomposition of \(H\) into subgraphs isomorphic to \(G\). If \(H\) has a \(G\)-decomposition, \(H\) is said to be \(G\)-decomposable; this is denoted by \(H \rightarrow G\). In this paper, we prove by construction that the complete graph \(K_{24}\) is \(G\)-decomposable, where \(G\) is the complementary graph of the path \(P_5\).

A unified approach to prove former connectivity results of Tutte, Cunningham, Inukai, and Weinberg, Oxley, and Wagner.

This paper deals with the existence of \({Z}\)-cyclic Room squares of order \(2v\) (or of side \(2v-1\)) whenever \(2v-1 =\Pi_{i=1}^{n}p^{\alpha_i}\), ( \(p_i=2^{m_i}b_i+1\geq 7\) are distinct primes, \(b_i\) are odd, \(b_i > 1\), and \(\alpha_i\) are positive integers, \(i = 1, 2, \ldots, n\)), and includes some further results involving Fermat primes.

Let \(G\) be a connected \((p,q)\)-graph. Let \(\gamma_c\) denote the connected domination number of \(G\). In this paper, we prove that \(q\leq \lfloor\frac{p(p-\gamma_c)}{2}\rfloor\) and equality holds if and only if \(G = C_p\) or \(K_p\) or \(K_p – Q\) where \(Q\) is a minimum edge cover of \(K_p\). We obtain similar bounds on \(\gamma_q\) for graphs with given: Total domination number \(\gamma_t\) Clique domination number \(\gamma_k\) Edge domination number \(\gamma ‘\) Connected edge domination number \(\gamma’_{c }\) and for each of these parameters, characterize the class of graphs attaining the corresponding bound.

We consider all \(2-(v,3)\) trades in which every pair appears at most once in each part of the trade, and we call them Steiner Triple Trades \({STT}(v)\). We completely classify \({STT}(v)\) with \(6 \leq vol(T) \leq 9\).

Let \(G\) be a graph. A function \(f: V(G) \to \{1, 2, \ldots, k\}\) is a \(k\)-ranking for \(G\) if \(f(u) = f(v)\) implies that every \(u-v\) path \(P\) contains a vertex \(w\) such that \(f(w) > f(u)\). A function \(f: V(G) \to \{1, 2, \ldots, 4\}\) is a minimal \(k\)-ranking if \(f\) is a \(k\)-ranking and for any \(x\) such that \(f(x) > 1\) the function \(g(z) = f(z)\) for \(z \neq x\) and \(1 \leq g(x) < f(x)\) is not a \(k\)-ranking. This paper establishes further properties of minimal rankings, gives a procedure for constructing minimal rankings, and determines, for some classes of graphs, the minimum value and maximum value of \(k\) for which \(G\) has a minimal \(k\)-ranking. In addition, we establish tighter bounds for the minimum value of \(k\) for which \(G\) has a \(k\)-ranking.

A tournament is a complete directed graph. A convex subset is a vertex subset with the property that every two-path beginning and ending inside the convex subset is contained completely within the subset. This paper shows a relationship between convex subsets and transitive closures which leads to an optimal \(O(n^3)\)-time algorithm for finding all convex subsets in a tournament.

Let \({A}(n,3)\) denote the \(n\)-dimensional affine space over the finite field of order three. In this paper, we use basic combinatorial principles to discuss some old and new results about the lines in \({A}(3,3)\). For \(S \subset {A}(3,3)\), let \(||S||_3\) and \(||S||_{3,k}\) respectively denote the number of lines and the number of \(k\)-lines of \({A}(3,3)\) contained entirely in \(S\). For each \(t\), we compute \(\alpha_3(t) = \min\{||S||_3 : |S| = t\}\) and \(\Omega_3(t) = \max\{||S||_3 : |S| = t\}\). We also give results about \(\alpha_{3,k}(t) = \min\{||S||_{n,k} : |S| = t\}\) and \(\omega_{3,k}(t) = \max\{||S||_{n,k} : |S| = t\}\) and results about \(1\)-lines and \(n\)-lines in \({A}(n,3)\).

The binary linear code of a Steiner triple system on \(2^d – 1\) points, where \(d \geq 3\) is an integer, contains a copy of the Hamming code \(\mathcal{H}_{di}\) this fact can be used to characterize those systems on \(2^d – 1\) points that have low dimension, and to show that these systems can always be extended to Steiner quadruple systems whose binary code is the extended code of the Steiner triple system.

Let \(m\) and \(n\) be positive integers, and let \(\mathbf{R} = (r_1, \ldots, r_m)\) and \(\mathbf{S} = (s_1, \ldots, s_n)\) be nonnegative integral vectors with \(r_1 + \cdots + r_m = s_1 + \cdots + s_n\). Let \(\mathbf{Q} = (q_{ij})\) be an \(m \times n\) nonnegative integral matrix. Denote by \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\) the class of all \(m \times n\) nonnegative integral matrices \(\mathbf{A} = (a_{ij})\) with row sum vector \(\mathbf{R}\) and column sum vector \(\mathbf{S}\) such that \(a_{ij} \leq q_{ij}\) for all \(i\) and \(j\). We study a condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\). The well known existence theorem follows from the max-flow-min-cut theorem. It contains an exponential number of inequalities. By generalizing the Gale-Ryser theorem, we obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. We build a kind of hierarchy of theorems: under weaker and weaker conditions, a (larger and larger) polynomial (in \(n\)) number of inequalities yield a necessary and sufficient condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\).

Let \(G = (V, E)\) be a graph and let \(\mathcal{H}\) be a set of graphs. A set \(S \subseteq V\) is \(\mathcal{H}\)-independent if for all \(H \in \mathcal{H}\), \(\langle S \rangle\) contains no subgraph isomorphic to \(H\). A set \(S \subseteq V\) is an \(\mathcal{H}\)-dominating set of \(G\) if for every \(v \in V – S\), \(\langle S \cup \{v\} \rangle\) contains a subgraph containing \(v\) which is isomorphic to some \(H \in \mathcal{H}\).

The \(\mathcal{H}\)-domination number of a graph \(G\), denoted by \(\gamma_{\mathcal{H}}(G)\), is the minimum cardinality of an \(\mathcal{H}\)-dominating set of \(G\) and the \(\mathcal{H}\)-independent domination number of \(G\), denoted by \(i_{\mathcal{H}}(G)\), is the smallest cardinality of an \(\mathcal{H}\)-independent \(\mathcal{H}\)-dominating set of \(G\).

A sequence of positive integers \(a_2 \leq \cdots \leq a_m\) is said to be a domination sequence if there exists a graph \(G\) such that \(\gamma_{(K_k)}(G) = a_k\) for \(k = 2, \ldots, m\). In this paper, we find an upper bound for \(\gamma_{\mathcal{H}}(G)\) and show that the problems of computing \(\gamma_{\{K_n\}}\) and \(i_{\{K_n\}}\) are NP-hard. Finally, we characterize nondecreasing sequences of positive integers which are domination sequences, and provide a sufficient condition for equality of \(\gamma_{\{K_n\}}(G)\) and \(i_{\{K_n\}}(G)\).

In this paper, we prove that the partial sums of the chromatic polynomial of a graph define an alternating sequence of upper and lower bounds.

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\).