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.

In this paper, we derive and present some necessary conditions for the existence of certain combinatorial arrays (called balanced arrays (\(B\)-arrays)) with two elements by making use of some classical inequalities. We discuss briefly the usefulness of these arrays in combinatorics and statistical design of experiments.

An explicit recurrence is obtained for the clique polynomial of a short ladder in which the two diagonals are drawn in each cell. From this result, an explicit formula for the number of decompositions of the ladder into triangles and \(4\)-cliques is obtained. The recurrence is then used to obtain results for the matching polynomial of the ladder. Finally, an association is made with a particular tiling problem.

Let \(G\) be a finite graph and \(x\) be its vertex. The \({neighbourhood}\) of \(x\) in \(G\), denoted \(N_G(x)\), is a subgraph of \(G\) induced by all vertices adjacent to \(x\). \(G\) is a \({graph \; with \; a \; constant \; neighbourhood}\) if there exists a graph \(H\) such that \(N_G(x)\) is isomorphic to \(H\) for every vertex \(x\) of \(G\).

We completely characterize graphs with constant neighbourhoods isomorphic to complements of regular disconnected graphs.

A \({numbering}\) of a graph \(G = (V, E)\) is a bijection \(f: V \rightarrow \{1, 2, \ldots, p\}\) where \(|V| = p\). The \({additive \; bandwidth \; of \; numbering}\) \(f\) is \(B^+(G, f) = \max\{|f(u) + f(v) – (p + 1)| : uv \in E\}\), and the \({additive \; bandwidth}\) of \(G\) is \(B^+(G) = \min\{B^+(G, f) : f \text{ a numbering of } G\}\). Labeling \(V\) by a numbering which yields \(B^+(G)\) has the effect of causing the \(1\)’s in the adjacency matrix of \(G\) to be placed as near as possible to the main counterdiagonal, a fact which offers potential storage savings for some classes of graphs. Properties of additive bandwidth are discussed, including relationships with other graphical invariants, its value for cycles, and bounds on its value for extensions of full \(k\)-ary trees.

Let \(\Gamma_\ell\) be the union of \(n\) complete graphs \(A_1, A_2, \ldots, A_n\) of size \(n\) each such that \(|A_i \cap A_j| \leq \ell\) whenever \(i \neq j\). We prove that the chromatic number of \(\Gamma_\ell\) is bounded above by \((2n – 4)\ell + 1\).

We deal with a family of undirected Cayley graphs \(X_n\) which are unions of disjoint Hamilton cycles, and some of their properties, where \(n\) runs over the positive integers. It is proved that \(X_n\) is a bipartite graph when \(n\) is even. If \(n\) is an odd number, we count the number of different colored triangles in \(X_n\).

There has been a great deal of interest in relating the rank of the adjacency matrix of a graph to other fundamental numbers associated with a graph. We present two results which may be helpful in guiding further development in this area. Firstly, we give a linear time algorithm for finding the rank of any tree which is twice its edge independence number. Secondly, we give a formula for the rank of any grid graph consisting of \(mn\) vertices arranged in a rectangular grid of \(m\) rows and \(n\) columns on a planar, cylindrical, or toroidal surface.

A labeling of the graph \(G\) with \(n\) vertices assigns integers \(\{1, 2, \ldots, n\}\) to the vertices of \(G\). This further induces a labeling on the edges as follows: if \(uv\) is an edge in \(G\), then the label of \(uv\) is the difference between the labels of \(u\) and \(v\). The \({bandwidth}\) of \(G\) is the minimum over all possible labellings of the maximum edge label. The NP-completeness of the bandwidth problem compels the exploration of heuristic algorithms. The Gibbs-Poole-Stockmeyer algorithm (GPS) is the best-known bandwidth reduction algorithm. We introduce a heuristic algorithm that uses simulated annealing to approximate the bandwidth of a graph. We compare labellings generated by our algorithm to those obtained from GPS. Test graphs include: trees, grids, windmills, caterpillars, and random graphs. For most graphs, labellings produced by our algorithm have significantly lower bandwidth than those obtained from GPS.

We define two complete sets \(\mathcal{L}\) and \(\mathcal{L}’\) of pairwise orthogonal \(9 \times 9\) Latin squares to be equivalent if and only if \(\mathcal{L}’\) can be obtained from \(\mathcal{L}\) by some combination of: (i) applying a permutation \(\theta\) to the rows of each of the \(8\) squares in \(\mathcal{L}\), (ii) applying a permutation \(\phi\) to the columns of each square from \(\mathcal{L}\), and (iii) permuting the symbols separately within each square from \(\mathcal{L}\).
We use known properties of the projective planes of order \(9\) to show that, under this equivalence relation, there are \(19\) equivalence classes of complete sets. For each equivalence class, we list the species and transformation sets of the \(8\) Latin squares in a complete set. As this information alone is not sufficient for determining the equivalence class of a given complete set, we provide a convenient method for doing this.

It is shown that for any even integer \(u \geq 20\), a Room frame of type \(2^{n}u^1\) exists if and only if \(n \geq u + 1\).

We show that for infinitely many \(n\), there exists a Cayley graph \(\Gamma\) of order \(n\) in which any two largest cliques have a nonempty intersection. This answers a question of Hahn, Hell, and Poljak. Further, the graphs constructed have a surprisingly small clique number \(c_\Gamma = \left\lfloor \sqrt{2n} \right\rfloor\) (and we do not know if the constant \(\sqrt{2}\) can be made smaller).

\(D\)-optimal exact designs in a completely randomized statistical set-up are constructed, for comparing \(n > 2\) qualitative factors (treatments), making \(r\) observations per treatment level in the presence of \(n\) (or less) quantitative or continuous factors (regression factors or covariates) of influence. Their relation with cyclic supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) is shown, when \(n = 2u \equiv 2 \pmod{4}\), \(r \equiv 1 \pmod{2}\), \(r \neq 1\), \(r < u\) and \(k_1, k_2, \lambda\) are defined by \(1 \leq k_1 \leq k_2 \leq (u-1)/2\), \((u-2k_1)^2 + (u-2k_2)^2 = 2(ur+u-r)\), \(\lambda = k_1 + k_2 – (u-r)/2\). Making use of known cyclic difference sets, the existence of a multiplier and the non-periodic autocorrelation function of two sequences, such supplementary difference sets are constructed for the first time. A list of all 201 supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) for \(n = 2u < 100\) is given.

In this paper, we consider a permutation \(\sigma \in S_n\) as acting on an arbitrary tree with \(n\) vertices (labeled \(1, 2, 3, \ldots, n\)). Each edge \([a, b]\) of \(T\) corresponds to a transposition \((a, b) \in S_n\), and such a “tree of transpositions” forms a minimal generating set for \(S_n\). If \(\sigma \in S_n\), then \(\sigma\) may be written as a product of transpositions from \(T, \sigma = t_k t_{k-1} \ldots t_2t_1\). We will refer to such a product as a \(T\)-factorization of \(\sigma\) of length \(k\). The primary purpose of this paper is to describe an algorithm for producing \(T\)-factorizations of \(\sigma\). Although the algorithm does not guarantee minimal factorizations, both empirical and theoretical results indicate that the factorizations produced are “nearly minimal”. In particular, the algorithm produces factorizations that never exceed the known upper bounds.

The linear vertex-arboricity of a surface \(S\) is the maximum of the linear vertex-arboricities of all graphs embeddable into \(S\). Poh showed that the linear vertex-arboricity of a sphere is three. We show that the linear vertex-arboricities of a projective plane and a torus are three and four, respectively. Moreover, we show that the linear vertex-arboricity of a Klein bottle is three or four.