Let \(R(n)\) denote the number of two-color partitions of \(n\). We obtain several identities concerning \(R(n)\).

We show that if \(M(n, m)\) denotes the time of a \((u, v)\)-minimum cut computation in a directed graph with \(n \geq 2\) nodes, \(m\) edges, and \(s\) and \(t\) are two distinct given nodes, then there exists an algorithm with \(O(n^2m+n\cdot M(n, m))\) running time for the directed minimum odd (or even) \((s, t)\)-cut problem and for its certain generalizations.

Basic properties of in-degree distribution of a general model of random digraphs \(D(n, \mathcal{P})\) are presented. Then some relations between random digraphs \(D(n, \mathcal{P})\) for different probability distributions \(\mathcal{P}\)’s are studied. In this context, a problem of the existence of a threshold function for every monotone digraph property of \(D(n, \mathcal{P})\) is discussed.

For a given structure (graph, multigraph, or pseudograph) \(G\) and an integer \(r \geq \Delta(G)\), a smallest inducing \(r\)-regularization of \(G\) (which is an \(r\)-regular superstructure of the smallest possible order, with bounded edge multiplicities, and containing \(G\) as an induced substructure) is constructed.

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of these extremal problems. We define a \((p, q, \lambda, \delta)\) graph as a graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \lambda, \delta)\) realizable if there is a \((p, q, \lambda, \delta)\) graph with \(p = a, q = b, \lambda = c\), and \(\delta = d\). Inequalities representing necessary and sufficient conditions for a quadruple to be \((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

An aperiodic perfect map (APM) is an array with the property that each possible array of certain size, called a window, arises exactly once as a subarray in the array. In this article, we give some constructions which imply a complete answer for the existence of APMs with \(2 \times 2\) windows for any alphabet size.

A \(4\)-regular graph \(G\) is called a \(4\)-circulant if its adjacency matrix \(A(G)\) is a circulant matrix. Because of the special structure of the eigenvalues of \(A(G)\), the rank of such graphs is completely determined. We show how all disconnected \(4\)-circulants are made up of connected \(4\)-circulants and classify all connected \(4\)-circulants as isomorphic to one of two basic types.

Let \([n, k, d; g]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \(\mathrm{GF}(g)\). Let \(d_8(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 8]\)-code for given values of \(n\) and \(k\). In this paper, twenty-two new linear codes over \(\mathrm{GF}(8)\) are constructed which improve the bounds on \(d_8(n, k)\).

We find new full orthogonal designs in order \(56\) and show that of
\(1285\) possible \(OD(56; s_1, s_2, s_3,56 – s_1 – s_2 – s_3)\) \(163\) are known, of
\(261\) possible \(OD(56; s_1, s_2, 56 – s_1 – s_2)\) \(179\) are known. All possible
\(OD(56; s_1,56 – s_1)\) are known.

Sattolo has presented an algorithm to generate cyclic permutations at random. In this note, the two parameters “number of moves” and “distance” are analyzed.