A $(v,k,\lambda )$ covering design is a set of $b$ blocks of size $k$ such that each pair of points occurs in at least $\lambda$ blocks, and the covering number $C(v,k,\lambda )$ is the minimum value of $b$ in any $(v,k,\lambda )$ covering design. For $k=5$ and $v$ even, there are 24 open cases with $2\le \lambda \le 21$, each of which is the start of an open series for $\lambda ,\lambda +20,\lambda +40,\dots$. In this article, we solve 22 of these cases with $\lambda \le 21$, leaving open $(v,5,\lambda )=(44,5,13)$ and $(44,5,17)$ (and the series initiated for the former).

The basis number of a graph $G$ is defined to be the least integer $d$ such that there is a basis $\mathcal{B}$ of the cycle space of $G$ such that each edge of $G$ is contained in at most $d$ members of $\mathcal{B}$. MacLane [16] proved that a graph, $G$, is planar if and only if the basis number of $G$ is less than or equal to 2. Ali and Marougi [3] proved that the basis number of the strong product of two cycles and a path with a star is less than or equal to 4. In this work, (1) we prove the basis number of the strong product of two cycles is 3. (2) We give the exact basis number of a path with a tree containing no subgraph isomorphic to a 3-special star of order 7. (3) We investigate the basis number of a cycle with a tree containing no subgraph isomorphic to a 3-special star of order 7. The results in (1) and (2) improve the upper bound of the basis number of the strong product of two cycles and a star with a path which were obtained by Ali and Marougi.

A set $S$ of vertices is a total dominating set of a graph $G$ if every vertex of $G$ is adjacent to some vertex in $S$. The minimum cardinality of a total dominating set is the total domination number ${\gamma }_t(G)$. We show that for a nontrivial tree $T$ of order $n$ and with $\ell$ leaves, ${\gamma }_t(T)⩾\frac{n+2–\ell }{2}$, and we characterize the trees attaining this lower bound.

This paper presents a computationally efficient algorithm for solving the following well-known die problem: Consider a “crazy die” to be a die with $n$ faces where each face has some “cost”. Costs need not be sequential. The problem is to determine the exact probability that the sum of costs from $U$ throws of this die is $\ge T$, $T\in \mathbb{R}$. Our approach uses “slice” volume computation in $U$-dimensional space. Detailed algorithms, complexity analysis, and comparison with traditional generating functions approach are presented.

Difference systems of sets (DSS), introduced by Levenshtein, are used to design code synchronization in the presence of errors. The paper gives a new lower bound of DSS’s size.

In a loop transversal code, the set of errors is given the structure of a loop transversal to the linear code as a subgroup of the channel. A greedy algorithm for specifying the loop structure, and thus for the construction of loop transversal codes, was discussed by Hummer et al. Apart from some theoretical considerations, the focus was mainly on error correction, in the white noise case constructing codes with odd minimum distance. In this paper, an algorithm to compute loop transversal codes with even minimum distance is given. Some record-breaking codes over a 7-ary alphabet are presented.

Let $a,b$ be two positive integers. For the graph $G$ with vertex set $V(G)$ and edge set $E(G)$ with $p=|V(G)|$ and $q=|E(G)|$, we define two sets $Q(a)$ and $P(b)$ as follows:

$$Q(a)=\{\begin{array}{ll}\{\pm a,\pm (a+1),\dots ,\pm (a+\frac{q-2}{2})\}& \text{if }q\text{ is even}\\ \{0\}\cup \{\pm a,\pm (a+1),\dots ,\pm (a+(q-3)/2)\}& \text{if }q\text{ is odd}\end{array}$$

$$P(b)=\{\begin{array}{ll}\{\pm b,\pm (b+1),\dots ,\pm (b+(p-2)/2)\}& \text{if }p\text{ is even}\\ \{0\}\cup \{\pm b,\pm (b+1),\dots ,\pm (b+(\frac{p-3}{2})/2)\}& \text{if }p\text{ is odd}\end{array}$$

For the graph $G$ with $p=|V(G)|$ and $q=|E(G)|$, $G$ is said to be $Q(a)P(b)$-super edge-graceful (in short $Q(a)P(b)$-SEG), if there exists a function pair $(f,f^{+})$ which assigns integer labels to the vertices and edges; that is, $f^{+}:V(G)\to P(b)$, and $f:E(G)\to Q(a)$ such that $f^{+}$ is onto $P(b)$ and $f$ is onto $Q(a)$, and

$$f^{+}(u)=\sum \{f(u,v):(u,v)\in E(G)\}.$$

We investigate $Q(a)P(b)$ super edge-graceful graphs.

Let $A$ be a non-trivial abelian group. We call a graph $G=(V,E)$ $A$-magic if there exists a labeling $f:E(G)\to A\setminus \{0\}$ such that the induced vertex set labeling $f^{+}:V(G)\to A$, defined by $f^{+}(v)=\sum f(u,v)$ where the sum is over all $(u,v)\in E(G)$, is a constant map. In this paper, we show that $K_{k_1,k_2,\dots ,k_n}$ (where $K_i\ge 2$) is $A$-magic, for all $A$ where $|A|\ge 3$.

We define 1 new type of resolvability called $\alpha$-pair-resolvability in which each point appears in each resolution class as a member of $\alpha$-pairs. The concept is intended for path designs (or other designs) in which the role of points in blocks is not uniform or for designs which are not balanced. We determine the necessary conditions and show they are sufficient for $k=3$ and $\alpha =2,3$ ($\alpha \ge 2$ is necessary in every case). We also consider near $a$-pair-resolvability and show the necessary conditions are sufficient for $\alpha =2,4$. We consider under what conditions it is possible for the ordered blocks of a path design to be considered as unordered blocks and thereby create a triple system (a tight embedding) and there also we show the necessary conditions are sufficient. We show it is always possible to embed maximally unbalanced path designs $\text{PATH}(v,3,1)$ into $\text{PATH}(v+s,3,1)$ for admissible $s$, and to embed any $\text{PATH}(v,3,2\lambda )$ into a $\text{PATH}(v+s,3,2\lambda )$ for any $s\ge 1$.

Recent developments in logic programming are based on bilattices (algebras with two separate lattice structures). This paper provides characterizations and structural descriptions for bilattices using the algebraic concepts of superproduct and hyperidentity. The main structural description subsumes the many variants that have appeared in the literature.

The Ramsey number $R(C_4,B_n)$ is the smallest positive integer $m$ such that for every graph $F$ of order $m$, either $F$ contains $C_4$ (a quadrilateral) or $\overline{F}$ contains $B_n$ (a book graph $K_2+\overline{K_n}$ of order $n+2$). Previously, we computed $R(C_4,B_n)=n+9$ for $8\le n\le 12$. In this continuing work, we find that $R(C_4,B_{13})=22$ and surprisingly $R(C_4,B_{14})=24$, showing that their values are not incremented by one, as one might have suspected. The results are based on computer algorithms.

Comma-free codes are used to correct synchronization errors in sequential transmission. Systematic comma-free codes have codewords with fixed positions for error correction. We consider only comma-free codes with constant word length $n>1$. Circular codes use the integers mod $n$ as indices for codeword entries. We first show two easily stated conditions are equivalent to the existence question for circular systematic comma-free codes over arbitrary finite alphabets. For $n>3$ a family of circular systematic comma-free codes with word length $n=p$, a prime, is constructed, each corresponding to a fair partition of a difference set in ${\mathbb{Z}}_n$.

This paper gives the exact size of edit spheres of radius 1 and 2 for any word over a finite alphabet. Structural information about the edit metric space, in particular a representation as a pyramid of hypercubes, will be given. The 1-spheres are easy to understand, being identical to 1-spheres over the Hamming metric. Edit metric 2-spheres are much more complicated. The size of a 2-sphere hinges on the structure of the word at its center. That is, the word’s length, number of blocks, and most importantly (and troublesome) the number of locally maximal alternating substrings (LMAS) of each length. An alternating substring switches back and forth between two characters, e.g. 010101, and is maximal if it is contained in no other such substring. This variation in sphere size depending on center characteristics is what truly separates the algebraic character of codes over the edit metric from those over the Hamming metric.

We determine some coefficients of the flow polynomial of the complete graph $K_n$.

Groups provide the mathematical language for exact symmetry. Applications in biology and other fields are now raising the problem of developing a rigorous theory of approximate symmetry. In this paper, it is shown how approximate symmetry is determined by a quasigroup.

A graph has the neighbour-closed-co-neighbour, or ncc property, if for each of its vertices $x$, the subgraph induced by the neighbour set of $x$ is isomorphic to the subgraph induced by the closed non-neighbour set of $x$. Graphs with the ncc property were characterized in [1] by the existence of a locally $C_4$ perfect matching $M$: every two edges of $M$ induce a subgraph isomorphic to $C_4$. In the present article, we investigate variants of locally $C_4$ perfect matchings. We consider the cases where pairs of distinct edges of the matching induce isomorphism types including $P_4$, the paw, or the diamond. We give several characterizations of graphs with such matchings. In addition, we supply characterizations of graphs with matchings whose edges satisfy a prescribed parity condition.

In this paper we obtain some necessary conditions for the existence of balanced arrays (B-arrays) with two symbols and having strength seven. We then describe how these conditions involving the parameters of the array can be used to obtain an upper bound on the constraints of such arrays, and give some illustrative examples to this effect.

A defensive alliance in a graph $G(V,E)$ is a set of vertices $S\subseteq V$ such that for every vertex $v\in S$, the closed neighborhood $N_G[v]$ of $v$ has at least as many vertices in $S$ as it has in $V–S$. An offensive alliance is a set of vertices $S\subseteq V$, such that for every vertex $v$ in the boundary $\mathrm{\partial }(S)$ of $S$ the number of neighbors that $v$ has in $S$ is greater than or equal to the number of neighbors it has in $V–S$. A subset of vertices which is both an offensive and a defensive alliance is called a powerful alliance. An alliance which is also a dominating set is called a global alliance. In this paper, we show that finding an optimal defensive (offensive, powerful) global alliance is an NP-hard problem.

We discuss a branch of Ramsey theory concerning vertex Folkman numbers and how computer algorithms have been used to compute a new Folkman number. We write $G\to (a_1,\dots ,a_k{)}^v$ if for every vertex $k$-coloring of an undirected simple graph $G$, a monochromatic $K_{a_i}$ is forced in color $i\in \{1,\dots ,k\}$. The vertex Folkman number is defined as$F_v(a_1,\dots ,a_k;p)=\text{min}\{|V(G)|:G\to (a_1,\dots ,a_k{)}^v\wedge K_p⊈G\}.$ Folkman showed in 1970 that this number exists for $p>\text{max}\{a_1,\dots ,a_k\}$. Let $m=1+\sum _{i=1}^k(a_i–1)$ and $a=\text{max}\{a_1,\dots ,a_k\}$, then $F_v(a_1,\dots ,a_k;p)=m\text{ for }p>m,$ and $F_v(a_1,\dots ,a_k;p)=a+m\text{ for }p=m.$For $p<m$ the situation is more difficult and much less is known. We show here that, for a case of $p=m–1$, $F_v(2,2,3;4)=14$.

By analogy with Stirling numbers, tri-restricted numbers of the second kind count the number of partitions of a given set into a given number of parts, each part being restricted to at most three elements. Tri-restricted numbers of the first kind are then defined as elements of the matrix inverse to the matrix of tri-restricted numbers of the second kind. A new recurrence relation for the tri-restricted numbers of the second kind is presented, with a combinatorial proof. In answer to a problem that has remained open for several years, it is then shown by determinantal techniques that the tri-restricted numbers of the first kind also satisfy a recurrence relation. This relation is used to obtain a reciprocity theorem connecting the two kinds of tri-restricted number.