Let \(X\) be a graph and let \(\alpha(X)\) and \(\alpha'(X)\) denote the domination number and independent domination number of \(X\), respectively. We show that for every triple \((m,k,n)\), \(m \geq 5\), \(2 \leq k \leq m\), \(n > 1\), there exist \(m\)-regular \(k\)-connected graphs \(X\) with \(\alpha'(X) – \alpha(X) > n\). The same also holds for \(m = 4\) and \(k \in \{2,4\}\).

Let \(k\) be an integer greater than one. A set \(S\) of integers is called \(k\)-multiple-free (or \(k\)-MF for short) if \(x \in S\) implies \(kx \notin S\). Let \(f_k(n) = \max\{|A| : A \subseteq [1,n] \text{ is } k\text{-MF}\}\). A subset \(A\) of \([1,n]\) with \(|A| = f_k(n)\) is called a maximal \(k\)-MF subset of \([1,n]\). In this paper, we give a recurrence relation and a formula for \(f_k(n)\). In addition, we give a method for constructing a maximal \(k\)-MF subset of \([1,n]\).

This paper concerns the domination numbers \(\gamma_{k,n}\) for the complete \(k \times n\) grid graphs for \(1 \leq k \leq 10\) and \(n \geq 1\). These numbers were previously established for \(1 \leq k \leq 4\). Here we present dominating sets for \(5 \leq k \leq 10\) and \(n \geq 1\). This gives upper bounds for \(\gamma_{k,n}\) for \(k\) in this range. We discuss evidence that indicates that these upper bounds are also lower bounds.

By a graph we mean an undirected simple graph. The genus \(\gamma(G)\) of a graph \(G\) is the minimum genus of the orientable surface on which \(G\) is embeddable. The thickness \(\Theta(G)\) of \(G\) is the minimum number of planar subgraphs whose union is \(G\).

In [1], it is proved that, if \(\gamma(G) = 1\), then \(\Theta(G) = 2\). If \(\gamma(G) = 2\), the known best upper bound on \(\Theta(G)\) is \(4\) and, as far as the author knows, the known best lower bound is \(2\). In this paper, we prove that, if \(\gamma(G) = 2\), then \(\Theta(G) \leq 3\).

A generalization of (binary) balanced incomplete block designs is to allow a treatment to occur in a block more than once, that is, instead of having blocks of the design as sets, allow multisets as blocks. Such a generalization is referred to as an \(n\)-ary design. There are at least three such generalizations studied in the literature. The present note studies the relationship between these three definitions. We also give some results for the special case when \(n\) is \(3\).

We investigate searching strategies for the set \(\{1, \ldots, n\}\) assuming a fixed bound on the number of erroneous answers and forbidding repetition of questions. This setting models the situation when different processors provide answers to different tests and at most \(k\) processors are faulty. We show for what values of \(k\) the search is feasible and provide optimal testing strategies if at most one unit is faulty.

Ramsey’s Theorem implies that for any graph \(H\) there is a least integer \(r = r(H)\) such that if \(G\) is any graph of order at least \(r\) then either \(G\) or its complement contains \(H\) as a subgraph. For \(n<r\) and \(0 \leq e \leq \frac{1}{2}n(n-1)\), let \(f(e) =1\) {if every graph \(G\) of order \(n\) and size \(e\) is such that either \(G\) or \(\overline{G}\) contains \(H\),} and let \(f(e)=0\) {otherwise.} This associates with the pair \((H,n)\) a binary sequence \(S(H,n)\). By an interval of \(S(H,n)\) we mean a maximal string of equal terms. We show that there exist infinitely many pairs \((H,n)\) for which \(S(H,n)\) has seven intervals.

In this paper the existence of the \(12140\) non-isomorphic symmetric \((49,16,5)\) designs with an involutory homology (this is a special kind of involution acting on a design) is propagated. The automorphism groups are cyclic of orders \(2\), \(4\), \(8\), or \(10\). \(218\) designs are self-dual. The \(40\) designs with an automorphism group of order \(10\) were already given in [2]. A computer (IBM \(3090\)) was used for about \(36\) hours CPU time. According to [2,4] now there are known \(12146\) symmetric \((49,16,5)\) designs.

This paper deals with the joint distributions of some characteristics of the two-dimensional simple symmetric random walk in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, and west with equal probability.

In \(1974\), G. Chartrand and R.E. Pippert first defined locally connected and locally \(n\)-connected graphs and obtained some interesting results. In this paper we first extend these concepts to digraphs. We obtain generalizations of some results of Chartrand and Pippert and establish relationships between local connectedness and global connectedness in digraphs.