In this paper, we investigate the relationship between the profiles of Hadamard matrices and the weights of the doubly even self-orthogonal/dual $[n,m,d]$ codes from Hadamard matrices of order $n=8t$ with $t\ge 1$. We show that such codes have $m\le \frac{n}{2}$, and give some computational results of doubly even self-orthogonal/dual $[n,m,d]$ codes from Hadamard matrices of order $n=8t$, with $1\le t\le 9$.

Let $G$ be a finite strongly connected mixed graph (i.e., a graph with both undirected and directed edges, in which each vertex can be reached from every other vertex if directed edges can only be traversed in their direction of orientation). We establish a necessary and sufficient condition for it to be possible to transform some undirected edges of $G$ into directed edges so that each vertex becomes the head of a prescribed number of newly directed edges and $G$ remains strongly connected. A special case of this result yields a new proof (not requiring matroid techniques) of a necessary and sufficient condition for it to be possible to split each vertex of a finite connected graph into a prescribed number of vertices whilst preserving connectedness.

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 $\mathrm{\Delta }(G)>\frac{3}{4}|V(G)I–\frac{1}{2}$, then ${\chi }_T(G)\le \mathrm{\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\ge 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\ge 2$, then $i_n(G)\le (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\ge 2n+1$ vertices, then ${\gamma }_n(G)\le p/(n+1)$ and that $i_n(G)+n{\gamma }_n(G)\le p$. Finally, it is shown that if $T$ is a tree on $p\ge 2n+1$ vertices, then $i_n(G)+n{\gamma }_n^t(G)\le 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\ge 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 )\ge \lceil \frac{v}{k}\lceil \frac{v-1}{k-1}\lambda \rceil \rceil =\varphi (v,k,\lambda )$, where $\lceil x\rceil$ is the smallest integer satisfying $x\le \lceil x\rceil$. It is shown here that $\alpha (v,5,7)=\varphi (v,5,7)$ for all positive integers $v\ge 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\le 7$.

Let $g$ and $f$ be integer-valued functions defined on $V(G)$ with $f(v)\ge g(v)\ge 1$ for all $v\in V(G)$. A graph $G$ is called a $(g,f)$-graph if $g(v)\le d_G(v)\le 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\ge 2$, every $((2mg+2m-2)t+(g+1)s,(2mf-2m+2)t+(f-1)s)$-graph $G$ is $(g,f)$-factorable. (ii) Let $g(x)$ be even and $m>2$. (1) If $m$ is even, and $G$ is a $((2mg+2)t+(g+1)s,(2mf-2m+4)t+(f-1)s)$-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 $((2mg+2m-4)t+(g+1)s,(2mf-2)t+(f-1)s)$-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.