In this paper, we derive some inequalities on the existence of balanced arrays (B-arrays) of strength six and with two symbols by using some results involving moments from Statistics. Besides providing illustrative examples, we will make brief comments on the use of these combinatorial arrays in Statistical Design of Experiments.

We estimate the number of labelled loop-free Eulerian oriented graphs with multiple edges with \(n\) vertices by using an \(n\)-dimensional Cauchy integral. An asymptotic formula is obtained for the case where the multiplicity of each edge is \(O(\log n)\).

The number of hypohamiltonian and that of hypotraceable \(n\)-vertex digraphs are both bounded below by a superexponential function of \(n\) for \(n \geq 6\) and \(n \geq 7\), respectively.

In a graph \(G = (V, E)\), a set \(S \subset V\) is a dominating set if each vertex of \(V – S\) is adjacent to at least one vertex in \(S\).

Approximately 1000 papers have been written on domination-related concepts, with more than half of them appearing in the literature in the last five years. Obviously, a comprehensive survey is beyond the scope of this paper, so a brief overview is presented.

Let \(G\) be a cubic graph containing no subdivision of the Petersen graph. If \(G\) has a \(2\)-factor \(F\) consisting of two circuits \(C_1\) and \(C_2\) such that \(C_1\) is chordless and \(C_2\) has at most one chord, then \(G\) is edge-\(3\)-colorable.

This result generalizes an early result by Ellingham and is a partial result of Tutte’s edge-\(3\)-coloring conjecture.

Let \(f(n,k)\) be the maximum chromatic number among all graphs whose edge set can be covered by \(n\) copies of \(K(n)\), the complete graph on \(n\) vertices, so that any two of those \(K(n)\) share at most \(k\) vertices.

It has been known that \(f(n,k) = (1 – o(1)).n^{{3}/{2}}\) for \(k \geq n^{{1}/{2}}\). We show that
\[(1 – o(1))n.k \leq f(n,k) \leq (k+1)(n-k)\]
for \(k < n^{{1}/{2}}\), hence, for \({1}/{k} = o(1)\), \[f(n,k) = (1 + o(1))n.k.\]

A string is strongly square-free if it contains no Abelian squares; that is, adjacent substrings which are permutations of each other. We discuss recent results concerning the construction of strongly square-free finite strings.

It is shown that the circuit polynomial characterizes many of the well-known families of graphs. These include chains, stars, cycles, complete graphs, regular complete bipartite graphs, and wheels. Some analogous results are deduced for the characteristic polynomial and the \(\mu\)-polynomial.

A connected dominating set is a dominating set \(S\) with the additional property that the subgraph induced by \(S\) is connected. We are interested in the collection C of graphs in which every minimal connected dominating set is of one size.
Trees, for instance, clearly belong to this collection. A partial characterization will be discussed; in particular, we determine those graphs which have the property that all spanning trees have the same number of leaves. It is noted that membership in this sub-collection of C can be determined in polynomial time.

A continuum with finitely many non-cut points is an irreducible tree. A two-variable power series for the number of (unlabelled) irreducible trees with \(p\) pendant and \(q\) interior vertices.


The result is then specialized to get Harary's series for the number of irreducible trees with \(n\) vertices and to another series for the number of irreducible trees with \(p\) pendant vertices, a result of interest in continuum theory.

The theory of lifting voltage digraphs provides a useful tool for constructing large digraphs with specified properties from suitable small base digraphs endowed with an assignment of voltages (= elements of a finite group) on arcs.
We revisit the degree/diameter problem for digraphs from this new perspective and prove a general upper bound on the diameter of a lifted digraph in terms of properties of the base digraph and voltage assignment.
In addition, we demonstrate that all currently known largest vertex-transitive Cayley digraphs for semidirect products of groups can be described by means of a voltage assignment construction using simpler groups.

The “characteristic” of a graph—the number of vertices, minus the number of edges, plus the number of triangles, etc.—is a little-studied, overtly combinatorial graph parameter intrinsically related to chordal graphs and common neighborhoods of subgraphs. I also introduce a sequence of related “higher characteristic” parameters.

A \emph{least deviant path} between two vertices in a weighted graph is defined as a path that minimizes the difference between the largest and smallest edge weights on the path.
Algorithms are presented to determine the least deviant path. The fastest algorithm runs in \(O(|E|^{1.793})\), in the worst case. A type of two-dimensional binary search is used to achieve this running time.

An SOLS (self-orthogonal Latin square) of order \(n\) with \(n_i\) missing sub-SOLS (holes) of order \(h_i\) (\(1 \leq i \leq k\)), which are disjoint and spanning (i.e., \(\sum_{i=1}^{k} n_ih_i = n\)), is called a frame SOLS and denoted by \(\text{FSOLS}(h_1^{n_1}, h_2^{n_2}, \ldots, h_k^{n_k})\).
In this article, it is shown that an \(\text{FSOLS}(3^{n-u}3^1)\) exists if and only if \(n \geq 4\) and \(n \geq 1 + \frac{2u}{3}\), with seventeen possible exceptions \((n, u) =\{(5, 1)\}\) and \(\{(n, u) = (n, \lfloor \frac{3(n-1)}{2}\rfloor)\) for \((n \in \{6, 10, 14, 18, 22, 30, 34, 38, 42, 46, 54, 58, 62, 66, 70, 94\}\)\}.

It is straightforward to show that the full automorphism group of \(G \otimes K_n\) contains the Cartesian cross product of \(\text{Aut}(G)\) and \(S_n\). If \(\text{Aut}(G \otimes K_n)\) properly contains this cross product, then we will say that \(G \otimes K_n\) has a “rich” automorphism group. First, several conditions on \(G\) that ensure that \(G \otimes K_n\) has a rich automorphism group are given. Then, it is shown that these conditions are both necessary and sufficient for \(G \otimes K_n\) to have a rich automorphism group.

In this note, necessary and sufficient conditions are given for the existence of an equitable partial Steiner triple system \((S,T)\) on \(n\) symbols with exactly \(t\) triples, such that the leave of \((S,T)\) contains a \(1\)-factor if \(n\) is even and a near \(1\)-factor if \(n\) is odd.

A catalogue is presented which contains the graphs having order at most 10 which are critical with respect to the total chromatic number. A number of structural properties which cause these graphs to be critical are discussed, and a number of infinite classes of critical graphs are identified.

A total colouring of a graph \(G\) is a function assigning colours to the vertices and edges of \(G\) in such a way that no two adjacent or incident elements are assigned the same colour. The total chromatic number, \(\chi”(G)\), is the minimum number of colours which need to be assigned to obtain a total colouring of the graph \(G\).
A longstanding conjecture, made independently by Behzad [3] and Vizing [17], claims that
\[
\Delta(G) + 1 \leq \chi”(G) \leq \Delta(G) + 2
\]
where \(\Delta(G)\) is the maximum degree of \(G\). The lower bound is sharp, the upper bound remains to be proved. A graph \(G\) is said to be Type 1 if \(\chi”(G) = \Delta(G) + 1\) and is said to be Type 2 if \(\chi”(G) \geq \Delta(G) + 2\).

We define a graph \(G\) to be critical with respect to the total chromatic number if \(G\) is connected and \(\chi”(G – e) < \chi''(G)\) for every edge \(e\) in \(G\). In Section 1 of this paper we identify all small order critical graphs, the catalogue of graphs is presented as a table of diagrams. In Section 2 we study structural properties of these graphs in order to identify features which cause a graph to be Type 2.

Given \(m\) unit-capacity bins and a collection \(x(n)\) of \(n\) pieces, each with a positive size at most one, the dual bin packing problem asks for packing a maximum number of pieces into the \(m\) bins so that no bin capacity is
exceeded. Motivated by the NP-hardness of the problem, Coffman et al. proposed a class of heuristics, the \emph{prefix} algorithms, and analyzed its worst-case performance bound.
Bruno and Downey gave a probabilistic bound for the FFI algorithm (which is a prefix algorithm proposed by Coffman et al.), under the assumption that piece sizes are drawn from the uniform distribution over \([0, 1]\). In this article, we generalize their result: Let \(F\) be an \emph{arbitrary} distribution over \([0, 1]\), and let
\(x(n)\) denote a random sample of a random variable \(X\) distributed according to \(F\). Then, for any \(\varepsilon > 0\), there are \(\lambda > 0\) and \(N > 0\),
dependent only on \(m\), \(\varepsilon\), and \(F\), such that for all \(n \geq N\),
\begin{align*}
\Pr\left(\frac{{\mathrm{OPT}}(x(n), m)}{{\mathrm{PRE}}(x(n), m)} \leq 1 + \varepsilon\right)
&> 1 – Me^{-2\lambda n},
\end{align*}
where \(M\) is a universal constant.
Another probabilistic bound is also given for \(\frac{\mathrm{OPT}(x(n),m)}{\mathrm{PRE}(x(n),m)}\), under a
mild assumption of \(F\).

The distance of a vertex \(u\) in a connected graph \(G\) is defined by \(\sigma_G(u) := \sum_{v \in V(G)} d(u, v)\), and the distance of \(G\) is given by \(\sigma(G) = \frac{1}{2} \sum_{u \in V(G)} \sigma(u) (= \sum_{\{u,v\} \subseteq V(G)} d(u, v)\). Thus, the average distance between vertices in a connected graph \(G\) of order \(n\) is \(\frac{\sigma(G)}{\binom{n}{2}}\). These graph invariants have been studied for the past fifty years. Here, we discuss some known properties and present a few new results, together with several open problems. We focus on trees.

Let \(\chi^*(G)\) denote the minimum number of colors required in a coloring \(c\) of the vertices of \(G\) where for adjacent vertices \(u, v\) we have \(c(N_G[u]) \neq c(N_G[v])\) when \(N_G[u] \neq N_G[v]\) and \(c(u) \neq c(v)\) when \(N_G[u] = N_G[v]\). We show that the problem of deciding whether \(\chi^*(G) \leq n\), where \(n \geq 3\), is NP-complete for arbitrary graphs. We find \(\chi^*(G)\) for several classes of graphs, including bipartite graphs, complete multipartite graphs, as well as cycles and their complements. A sharp lower bound is given for \(\chi^*(G)\) in terms of \(\chi(G)\) and an upper bound is given for \(\chi^*(G)\) in terms of \(\Delta(G)\). For regular graphs with girth at least four, we give substantially better upper bounds for \(\chi^*(G)\) using random colorings of the
vertices.

A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward \(\Theta(n^2)\) algorithm which computes all the weak repetitions in a given string of length \(n\) defined
on an arbitrary alphabet \(A\). Using results on Fibonacci and other simple strings, we prove that this algorithm is asymptotically optimal over all known encodings of the output.

An algorithm is presented which, when given the non-isomorphic designs with given parameters, generates all the trades in each of the designs. The lists of trades generated by the algorithm were used to find the sizes, previously unknown, of smallest defining sets of the \(21\) non-isomorphic \(2\)-(10, 5, 4) designs. Consideration of trades in a design to isomorphic and to non-isomorphic designs led to two variations on the concept of
defining sets. The lists of trades were then used to find the sizes of these smallest member and class defining sets, for five parameter sets.