The Balanced Network Search (BNS) is an algorithm which finds a maximum balanced flow in a balanced network \({N}\). This algorithm is a way of using network flows to solve a number of standard problems, including maximum matchings, the factor problem, maximum capacitated \(b\)-matchings, etc., in general graphs. The value of a maximum balanced flow equals the capacity of a minimum balanced edge-cut. Flow-carrying balanced networks contain structures called generalized blossoms. They are not based on odd cycles. Rather they are the connected components of a residual sub-network of \({N}\). An algorithm is given for finding a maximum balanced flow, by constructing complementary pairs of valid augmenting paths.

The total chromatic number \(\chi_T(G)\) of a graph \(G\) is the least number of colours needed to colour the edges and vertices of \(G\) so that no incident or adjacent elements receive the same colour. This paper shows that if \(G\) has maximum degree \(\Delta(G) > \frac{3}{4} |V(G)I – \frac{1}{2} \), then \(\chi_T(G) \leq \Delta(G) + 2\). A slightly weaker version of the result has earlier been proved by Hilton and Hind \([9]\). The proof here is shorter and simpler than the one given in \([9]\).

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(\mathcal{D}\) of vertices of \(G\) is an \(n\)-dominating set (total \(n\)-dominating) set of \(G\) if every vertex of \(V(G) – \mathcal{D}\) (\(V(G)\), respectively) is within distance \(n\) from some vertex of \(\mathcal{D}\) other than itself. The minimum cardinality among all \(n\)-dominating sets (respectively, total \(n\)-dominating sets) of \(G\) is called the \(n\)-domination number (respectively, total \(n\)-domination number) and is denoted by \(\gamma_n(G)\) (respectively, \(\gamma_n^t(G)\)). A set \(\mathcal{I}\) of vertices of \(G\) is \(n\)-independent if the distance (in \(G\)) between every pair of distinct vertices of \(\mathcal{I}\) is at least \(n+1\). The minimum cardinality among all maximal \(n\)-independent sets of \(G\) is called the \(n\)-independence number of \(G\) and is denoted by \(i_n(G)\). Suppose \(\mathcal{I}_k\) is an \(n\)-independent set of \(k\) vertices of \(G\) for which there exists a vertex \(v\) of \(G\) that is within distance \(n\) from every vertex of \(\mathcal{I}_k\). Then a connected subgraph of minimum size that contains the vertices of \(\mathcal{I}_k \cup \{v\}\) is called an \(n\)-generalized \(K_{1,k}\) in \(G\). It is shown that if \(G\) contains no \(n\)-generalized \(K_{1,3}\), then \(\gamma_n(G) = i_n(G)\). Further, it is shown if \(G\) contains no \(n\)-generalized \(K_{1,{k+1}}\), \(k \geq 2\), then \(i_n(G) \leq (k-1)\gamma_n(G) – (k-2)\). It is shown that if \(G\) is a connected graph with at least \(n + 1\) vertices, then there exists a minimum \(n\)-dominating set \(\mathcal{D}\) of \(G\) such that for each \(d \in \mathcal{D}\), there exists a vertex \(v \in V(G) – \mathcal{D}\) at distance \(n\) from \(d\) and distance at least \(n+1\) from every vertex of \(\mathcal{D} – \{d\}\). Using this result, it is shown if \(G\) is a connected graph on \(p \geq 2n+1\) vertices, then \(\gamma_n(G) \leq p/(n + 1)\) and that \(i_n(G) + n\gamma_n(G) \leq p\). Finally, it is shown that if \(T\) is a tree on \(p \geq 2n + 1\) vertices, then \(i_n(G) + n\gamma_n^t(G) \leq p\).

Let \(a, b, c\) be fixed, pairwise relatively prime integers. We investigate the number of non-negative integral solutions of the equation \(ax + by + cz = n\) as a function of \(n\). We present a new algorithm that computes the “closed form” of this function. This algorithm is simple and its time performance is better than the performance of yet known algorithms. We also recall how to approximate the abovementioned function by a polynomial and we derive bounds on the “error” of this approximation for the case \(a = 1\).

In this paper, scheduling problems with communication delays are considered. Formally, we are given a partial order relation \(\prec\) on a set of tasks \(T\), a set of processors \(P\), and a deadline \(d\). Supposing that a unit communication delay between two tasks \(a\) and \(b\) such that \(a \prec b\) occurs whenever \(a\) and \(b\) are scheduled on different processors, the question is: Can the tasks of \(T\) be scheduled on \(P\) within time \(d\)? It is shown here that the problem is NP-complete even if \(d = 4\). Also, for an unlimited number of processors, C. Picouleau has shown that for \(d = 8\) the problem is NP-complete. Here it is shown that it remains NP-complete for \(d \geq 6\) but is polynomially solvable for \(d < 6\), which closes the gap between P and NP for this problem, as regards the deadline.

Let \(V\) be a finite set of order \(v\). A \((v, k, \lambda)\) covering design of index \(\lambda\) and block size \(k\) is a collection of \(k\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks, \(\alpha(v, k, \lambda)\), in a covering design. It is well known that \(\alpha(v,k,\lambda) \geq \lceil\frac{v}{k}\lceil\frac{v-1}{k-1}\lambda\rceil\rceil = \phi(v, k, \lambda)\), where \(\lceil x \rceil\) is the smallest integer satisfying \(x \leq \lceil x \rceil\). It is shown here that \(\alpha(v,5,7) = \phi(v, 5, 7)\) for all positive integers \(v \geq 5\) with the possible exception of \(v = 22, 28, 142, 162\).

A graph \(G\) is called \(k\)-critical if \( \chi (G) = k\) and \( \chi (G – e) k\) is at most \(n – k + 3\) if \(k \leq 7\).

Let \(g\) and \(f\) be integer-valued functions defined on \(V(G)\) with \(f(v) \geq g(v) \geq 1\) for all \(v \in V(G)\). A graph \(G\) is called a \((g, f)\)-graph if \(g(v) \leq d_G(v) \leq f(v)\) for each vertex \(v \in V(G)\), and a \((g, f)\)-factor of a graph \(G\) is a spanning \((g, f)\)-subgraph of \(G\). A graph is \((g, f)\)-factorable if its edges can be decomposed into \((g, f)\)-factors.
The purpose of this paper is to prove the following three theorems: (i) If \(m \geq 2\), every \(\left((2mg+2m-2)t+(g+1)s, (2mf-2m+2)t+(f-1)s\right)\)-graph \(G\) is \((g, f)\)-factorable. (ii) Let \(g(x)\) be even and \(m > 2\). (1) If \(m\) is even, and \(G\) is a \(\left((2mg+2)t+(g+1)s, (2mf-2m+4)t+(f-1)s\right)\)-graph, then \(G\) is \((g, f)\)-factorable; (2) If \(m\) is odd, and \(G\) is a \(((2mg+4)t+(g+1)s$, $(2mf-2m+2)t+(f-1)s)\)-graph, then \(G\) is \((g, f)\)-factorable. (iii) Let \(f(x)\) be even and \(m > 2\). (1) If \(m\) is even, and \(G\) is a \(\left((2mg+2m-4)t+(g+1)s, (2mf-2)t+(f-1)s\right)\)-graph, then \(G\) is \((g, f)\)-factorable;
(2) If \(m\) is odd, and \(G\) is a \(((2mg+2m-2)t+(g+1)s\), \((2mf-4)t+(f-1)s)\)-graph, then \(G\) is \((g, f)\)-factorable.
where \(t\), \(m\) are integers and \(s\) is a nonnegative integer.

All Williamson matrices in this Note are symmetric circulants. Eight non-equivalent sets of Williamson matrices of order \(25\) are known. They were discovered by Williamson (\(2\) sets), Baumert and Hall (\(2\) sets), and Sawade (\(4\) sets). Sawade carried out a complete search and reported that there are exactly eight non-equivalent such sets of matrices. Subsequently, this was confirmed by Koukouvinos and Kounias. It is surprising that we have found two more such sets. Hence, there are ten non-equivalent sets of Williamson matrices of order \(25\).

Only three non-equivalent sets of Williamson matrices of order \(37\) were known so far. One of them was discovered by each of Williamson, Turyn, and Yamada. We have found one more such set.