We show that if, for any fixed \(r\), the neighbourhood unions of all \(r\)-sets of vertices are large enough, then \(G\) will have many edge-disjoint perfect matchings. In particular, we show that given fixed positive integers \(r\) and \(c\) and a graph \(G\) of even order \(n\), if the minimum degree is at least \(r + c – 1\) and if the neighbourhood union of each \(r\)-set of vertices is at least \(n/2 + \left(2\lfloor\frac{(c + 1)}{2}\rfloor – 1\right)r\), then \(G\) has \(c\) edge-disjoint perfect matchings, for \(n\) large enough. This extends earlier work by Faudree, Gould and Lesniak on neighbourhood unions of pairs of vertices.

In this paper, necessary and sufficient conditions for a vector to be the fine structure of a balanced ternary design with block size \(3\), index \(3\) and \(\rho_2 = 1\) and \(2\) are determined, with one unresolved case.

Let \(K^d_n\) be the product of \(d\) copies of the complete graph \(K_4\). Wojciechowski [4] proved that for any \(d \geq 2\) the hypercube \(K^d_2\) can be vertex covered with at most \(16\) disjoint snakes. We show that for any odd integer \(n \geq 3\), \(d \geq 2\) the graph \(K^d_n\) can be vertex covered with \(2n^3\) snakes.

Cwatsets are subsets of \(\mathbb{Z}^d_2\) which are nearly subgroups and which naturally appear in statistics and coding theory [8]. Each cwatset can be represented by a highly symmetric hypergraph [7]. We introduce and study the symmetry group of the hypergraph and connect it to the corresponding cwatset. We use this connection to establish structure theorems for several classes of cwatsets.

Bollobás, Brightwell [1] and independently Shi [3] proved the existence of a cycle through all vertices of degree at least \(\frac{n}{2}\) in any \(2\)-connected graph of order \(n\). The aim of this paper is to show that the above degree requirement can be relaxed for \(1\)-tough graphs.

In this paper we investigate the \(k\)th lower multiexponent \(f(n,k)\) for tournament matrices.
It was proved that \(f(m,3) = 2\) if and only if \(m \geq 11\). Thus the conjecture in [2] is disproved. Further we obtain a new sufficient condition for \(f(n,k) = 1\).

The cycle graph \(C(H)\) of a graph \(H\) is the edge intersection graph of all induced chordless cycles of \(H\). We investigate iterates of the mapping \(\overline{C}: G \rightarrow C(\overline{G})\) where \(C\) denotes the map that associates to a graph its cycle graph. We call a graph \(G\) vanishing under \(\overline{C}\) if \(\overline{C^n}(G) = 0\) for some \(n\), otherwise \(G\) is called \(\overline{C}\)-persistent. We call a graph \(G\) expanding under \(\overline{C}\) if \(|\overline{C^n}(G)| \to \infty\) as \(n \to \infty\). We show that the lowest order of a \(\overline{C}\)-expanding graph is \(6\) and determine the behaviour under \(\overline{C}\) of some special graphs, including trees, null graphs, cycles and complete bipartite graphs.

Nonbinary power residue codes are constructed using the relationship between these codes and quasi-cyclic codes. Eleven of these codes exceed the known lower bounds on the maximum possible minimum distance of a linear code.

In this paper the authors study one- and two-dimensional color switching problems by applying methods ranging from linear algebra to parity arguments, invariants, and generating functions. The variety of techniques offers different advantages for addressing the existence and uniqueness of minimal solutions, their characterizations, and lower bounds on their lengths. Useful examples for reducing problems to easier ones and for choosing tools based on simplicity or generality are presented. A novel application of generating functions provides a unifying treatment of all aspects of the problems considered.

Broadcasting refers to the process of information dissemination in a communication network whereby a message is to be sent from a single originator to all members of the network, subject to the restriction that a member may participate in only one message transfer during a given time unit. In this paper we present a family of broadcasting schemes over the odd graphs, \(O_{n+1}\). It is shown that the broadcast time of \(O_{n+1}\), \(b(O_{n+1})\), is bounded by \(2n\). Moreover, the conjecture that \(b(O_{n+1}) = 2n\) is put forward, and several facts supporting this conjecture are given.

We derive a formula for the expected value \(\mu(2n+1)\) of the independent domination number of a random binary tree with \(2n+1\) vertices and determine the asymptotic behavior of \(\mu(2n+1)\) as \(n\) goes to infinity.

In [5], Gueizow gave an example of semiboolean SQS-skeins of nilpotent class \(2\), all its derived sloops are Boolean “or” of nilpotence class \(1\). In this paper, we give an example of nilpotent SQS-skein of class \(2\) whose derived sloops are all of nilpotence class \(2\). Guelzow [6] has also given a construction of semiboolean SQS-skeins of nilpotence class \(n\) whose derived sloops are all of class \(1\). As an extension result, we prove in the present paper the existence of nilpotent SQS-skeins of class \(n\) all of whose derived sloops are nilpotent of the same class \(n\); for any positive integer \(n\).

In this note we solve almost completely a problem raised by Topp and Volkmann [7] concerning the product of the domination and the chromatic numbers of a graph.

The concept of a strong \(a\)-valuation was introduced by Maheo, who showed that if a graph \(G\) has a strong \(a\)-valuation, then so does \(G \times K_2\). We show that for various graphs \(G\), \(G \times Q_n\) has a strong \(a\)-valuation and \(G \times P_n\) has an \(a\)-valuation, where \(Q_n\) is the \(n\)-cube and \(P_n\) the path with \(n\) edges, including \(G = K_{m,2}\) for any \(m\). Yet we show that \(K_{m,n} \times K_2\) does not have a strong \(a\)-valuation if \(m\) and \(n\) are distinct odd integers.

Let \(p\) be an odd prime number. We introduce a simple and useful decoding algorithm for orthogonal Latin square codes of order \(p\). Let \({H}\) be the parity check matrix of orthogonal Latin square code. For any \({x} \in {GF}(p)^n\), we call \(2 {H}^t\) the syndrome of \({x}\). This method is based on the syndrome-distribution decoding for linear codes. In \(\mathcal {L}_p\), we need to find the first and the second coordinates of codeword in order to correct the errored received vector.

The maximum cardinality of a partition of the vertex set of a graph \(G\) into dominating sets is the domatic number of \(G\), denoted \(d(G)\). We consider Nordhaus-Gaddum type results involving the domatic number of a graph, where a Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. Thereafter we investigate the upper bounds on the sum and product of the domatic numbers \(d(G_1), d(G_2)\) and \(d(G_3)\) where \(G_1 \oplus G_2 \oplus G_3 = K_n\). We show that the upper bound on the sum is \(n+2\), while the maximum value of the product is \(\lceil \frac{n}{3} \rceil ^3\) for \(n > 57\).

Place a checker in some square of an \(n \times n\) checkerboard. The checker is allowed to step either to the east or to the north, and is allowed to step off the edge of the board in a manner suggested by the usual identification of the edges of the square to form a projective plane. We give an explicit description of all the routes that can be taken by the checker to visit each square exactly once.

Bailey (1989) defined a \(k \times v\) double Youden rectangle (DYR), with \(k 3\) is a prime power with \(k \equiv 3 \pmod{4}\). We now provide a general construction for DYRs of sizes \(k \times (2k+1)\) where \(k > 5\) is a prime power with \(k \equiv 1 \pmod{4}\). We present DYRs of sizes \(9 \times 19\) and \(13 \times 27\).

We show by an elementary argument that, given any greedy clique decomposition of a graph \(G\) with \(n\) vertices, the sum of the orders of the cliques is less than \(\frac{5}{8}n^2\). This gives support to a conjecture of Peter Winkler.

We study the signed domination number \(\gamma_s\), the minus domination number \(\gamma^-\) and the majority domination number \(\gamma_{\mathrm{maj}}\). In this paper, we establish good lower bounds for \(\gamma_s\), \(\gamma^-\) and \(\gamma_{\mathrm{maj}}\), and give sharp lower bounds for \(\gamma_s\), \(\gamma^-\) for trees.

In this paper, nineteen new binary linear codes are presented which improve the bounds on the maximum possible minimum distance. These codes belong to the class of quasi-cyclic (QC) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Six of the new codes meet the upper bound on minimum distance and so are optimal.

This game is a mixture of Searching and Cops and Robber. The Cops have partial information provided by sensing devices called photo radar. The Robber has perfect information. We give bounds on the number of photo radar units required by one Cop to capture a Robber on a tree and, with less tight bounds, on a copwin graph.

Cographs—complement-reducible graphs—can be viewed as intersection graphs (of \(k\)-dimensional boxes), as intersections of graphs (of \(P_4 ,C_4\)-free graphs), and as common tieset graphs of two-terminal graphs. This approach connects cographs with other topics such as chordal, interval, and series-parallel graphs, and it provides a natural dimension for cographs.

We consider reconstruction problems involving square-celled animals and other, similar, problems. Our main results, Corollary 3.2 and Theorem 3.3, give positive answers to the problems raised at the end of [4] by Harary and Manvel.

We present connections between \(T\)-colorings of graphs and regular vertex-coloring for distance graphs. Given a non-negative integral set \(T\) containing \(0\), a \(T\)-coloring of a simple graph assigns each vertex a non-negative integer (color) such that the difference of colors of adjacent vertices cannot fall in \(T\). Let \(\omega(T)\) be the minimum span of a \(T\)-coloring of an \(n\)-vertex complete graph. It is known that the asymptotic coloring efficiency of \(T\), \(R(T) = \lim_{n\to\infty} \frac{\omega(n)}{n}\), exists for any \(T\). Given a positive integral set \(D\), the distance graph \(G(\mathcal{Z}, D)\) has as vertex set all integers \(\mathbb{Z}\), and two vertices are adjacent if their difference is in \(D\). We prove that the chromatic number of \(G(\mathcal{Z}, D)\), denoted as \(\chi(\mathcal{Z}, D)\), is an upper bound of \(\lceil R(T) \rceil\), provided \(D=T \setminus \{0\}\). This connection is used in calculating \(\chi_a(m, k)\), chromatic number of \(G(\mathcal{Z},D)\) as \(D = \{1,2,3,\ldots,m\} \setminus \{k\}\), \(m > k\). Early results about \(\chi_\beta(m,k)\) were due to Eggleton, Erdos and Skilton [1985] who determined \(\chi_\beta(m,k)\) as \(k = 1\), partially settled the case \(k = 2\), and obtained upper and lower bounds for other cases. We show that \(\chi_\beta(m, k) = k\), if \(m < 2k\); and \(\chi_\beta(m,k) = \lceil \frac{m+k+1}{2} \rceil\), if \(m \geq 2k\) and \(k\) is odd. Furthermore, complete solutions for \(k = 2\) and \(4\), and partial solutions for other even numbers \(k\) are obtained. All the optimal proper colorings presented are periodic with smallest known periods.

The nonexistence of digraphs with order equal to the Moore bound \(\mathrm{M_{d,k}} = 1+d+\ldots+ d^h\) for \(d,k > 1\) has led to the study of the problem of the existence of “almost” Moore digraphs, namely digraphs with order close to the Moore bound. In [1], it was shown that almost Moore digraphs of order \(\mathrm{M_{d,k}} – 1\), degree \(d\), diameter \(k\) (\(d, k \geq 3\)) contain either no cycle of length \(k\) or exactly one such cycle. In this paper, we shall derive some further necessary conditions for the existence of almost Moore digraphs for degree \(d\) and diameter \(k \geq 1\). As a consequence, for diameter \(k = 2\) and degree \(d\), \(2 \leq d \leq 12\), we show that there are no almost Moore digraphs of order \(\mathrm{M_{d,2}} – 1\) with one vertex in a \(2\)-cycle \(C_2\) except the digraphs with every vertex in \(C_2\).

In this note we characterize the members of the Ramsey set \(\mathcal R(2K_2,tK_2)\) of all \((2K_2,tK_2)\)-minimal graphs using factor-critical graphs. Moreover, the sets \(\mathcal R(2K_2,tK_2)\) are determined for \(t \leq 5\).

Let \(G\) be a graph. A bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) is called a magic valuation if \(f(u)+f(v)+f(uv)\) is constant for any edge \(uv\) in \(G\). A magic valuation \(f\) of \(G\) is called a supermagic valuation if \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\). The following theorem is proved.For any graph \(H\), there exists a connected graph \(G\) so that \(G\) contains \(H\) as an induced subgraph and \(G\) has a supermagic valuation.

For a graph \(G\), let \(\alpha(G)\) and \(\tau(G)\) denote the independence number of \(G\) and the matching number of \(G\), respectively. Further, let \(G \times H\) denote the direct product (also known as Kronecker product, cardinal product, tensor product, categorical product, and graph conjunction) of graphs \(G\) and \(H\). It is known that \(\alpha(G \times H) \geq \max\{\alpha(G)-|H|, \alpha(H)-|G|\} =: \underline{\alpha}(G \times H)\) and that \(\tau(G \times H) \geq 2.\tau(G).\tau(H) =: \underline{\tau}(G \times H)\). It is shown that an equality/inequality between \(\alpha\) and \(\underline{\alpha}\) is independent of an equality/inequality between \(\tau\) and \(\underline{\tau}\). Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on \(\alpha(G \times H)\) that is achievable in certain cases.

All distinct double circulant self-dual codes over \(\text{GF}(5)\), with a minimum weight which is highest among all double circulant self-dual codes, have been found for each length \(n \leq 24\). For lengths \(14\), \(16\), and \(20\), these codes are extremal. In this paper, we characterize these extremal double circulant self-dual codes. In particular, a classification of extremal double circulant self-dual codes of length \(14\) is given. We present other double circulant codes which improve the lower bounds on the highest possible minimum weight. A classification of double circulant self-dual codes with parameters \([18, 9, 7]\) and \([24, 12, 9]\) is also given.