The queen’s graph $Q_n$ has the squares of the $n\times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let $\gamma (Q_n)$ be the minimum size of a dominating set of $Q_n$. Spencer proved that $\gamma (Q_n)\ge (n-1)/2$ for all $n$, and the author showed $\gamma (Q_n)=(n-1)/2$ implies $n\equiv 3(\mathrm{mod}4)$ and any minimum dominating set of $Q_n$ is independent.

Define a sequence by $n_1=3$, $n_2=11$, and for $i>2$, $n_i=4n_{i-1}–n_{i-2}–2$. We show that if $\gamma (Q_n)=(n-1)/2$ then $n$ is a member of the sequence other than $n_3=39$, and (counting from the center) the rows and columns occupied by any minimum dominating set of $Q_n$ are exactly the even-numbered ones. This improvement in the lower bound enables us to find the exact value of $\gamma (Q_n)$ for several $n$; $\gamma (Q_n)=(n+1)/2$ is shown here for $n=23,39$, and elsewhere for $n=27,71,91,115,131$.

A characterization of symmetric bent functions has been presented in [3]. Here, we provide a simple proof of the same result.

We prove that the total domination number of an $n$-vertex claw-free cubic graph is at most $n/2$.

This paper deals with the problem of labeling the edges of a plane graph in such a way that the weight of a face is the sum of the labels of the edges surrounding that face. The paper describes $(a,d)$-face antimagic labeling of a certain class of convex polytopes.

Below, we prove that there are exactly 244 nonisomorphic cyclic decompositions of the complete graph $K_{25}$ into cubes. The full list of such decompositions is given in the Appendix.

The magic square is probably the most popular and well-studied topic in recreational mathematics. We investigate a variation on this classic puzzle — the antimagic square. We review the history of the problem, and the structure of the design. We then present computational results on the enumeration and construction. Finally, we describe a construction for all orders.

We establish a necessary and sufficient condition for the existence of a perfect distance-$d$ placement in 3-dimensional tori, for both regular and irregular cases.

Let $G$ be a simple graph and $f$ a function from the vertices of $G$ to the set of positive integers. An $(f,n)$-coloring of $G$ is an assignment of $n$ colors to the vertices of $G$ such that each vertex $x$ is adjacent to less than $f(x)$ vertices with the same color as $x$. The minimum $n$ such that an $(f,n)$-coloring of $G$ exists is defined to be the $f$-chromatic number of $G$. In this paper, we address a study of this kind of locally restricted coloring.

A $G$-decomposition of the complete graph $K_v$ is a set $S$ of subgraphs of $K_v$, each isomorphic to $G$, such that the edge set of $K_v$ is partitioned by the edge sets of the subgraphs in $S$. For all positive integers $v$ and every 2-regular graph $G$ with ten or fewer vertices, we prove necessary and sufficient conditions for the existence of a $G$-decomposition of $K_v$.

A broadcast graph on $n$ vertices is a network in which a message can be broadcast in minimum possible ($=\lceil {\log }_{2}n\rceil$) time from any vertex. Broadcast graphs which have the smallest number of edges are called \emph{Minimum Broadcast Graphs}, and are subjects of intensive study. In this paper, we study how the number of edges in minimum broadcast graphs decreases, as we allow additional time over $\lceil {\log }_{2}n\rceil$.

We improve results obtained by Shastri in [15] and prove a conjecture posed by Shastri in [15, 16].

We give a new construction for skew-Hadamard matrices. This yields new infinite families of skew-Hadamard matrices, including 43 new skew-Hadamard matrices of order $4q<4000$.

The binary and ternary codes spanned by the rows of the point-by-block, pair-by-block, block-by-point incidence matrices of some 2-designs of small orders and their orthogonal complements are studied. Among some results, it is shown that if the code is properly chosen, then the weight distribution of the code serves as an appropriate design isomorphism invariant. The automorphism groups of the codes and the design are computed.

A Latin square of order $n$ is an $n\times n$ array of cells containing one of the $n$ elements in $\{1,2,\dots ,n\}$ such that in each row and each column each element appears exactly once. A partial transversal $P$ of a Latin square $L$ is a set of $n$ cells such that no two are in the same row and the same column. The number of distinct elements in $P$ is referred to as the length of $P$, denoted by $|P|$, and the maximum length of a partial transversal in $L$ is denoted by $t(L)$. In this paper, we study the technique used by Shor which shows that $t(L)\ge n–5.53{(\ln )}^2$ and we improve the lower bound slightly by using a more accurate evaluation.

The maximum possible toughness among graphs with $n$ vertices and $m$ edges is considered. This is an analog of the corresponding problem regarding maximum connectivity solved by Harary. We show that, if $m<\lceil \frac{3n}{2}\rceil$ or $m\ge n(\lfloor \frac{n}{6}\rfloor +\lfloor \frac{n\mathrm{mod}6}{3}\rfloor )$, then the maximum toughness is half of the maximum connectivity. The same conclusion is obtained if $r=\lfloor \frac{2m}{n}\rfloor \ge 1$ and $\frac{(n-1)(r+1)}{2}\le m<\frac{n(r+1)}{2}$. However, maximum toughness can be strictly less than half of maximum connectivity. Some values of maximum toughness are computed for $1\le n\le 12$, and some open problems are presented

We describe a random variable ${\text{D}}_{\text{{n,m}}}$, $\text{n}\ge \text{m}\ge 1$, as the number of failures until the first success in a sequence of n Bernoulli trials containing exactly m successes, for which all possible sequences containing m successes and n-m failures are equally likely. We give the probability density function, the expectation, and the variance of ${\text{D}}_{\text{{n,m}}}$. We define a random variable ${\text{D}}_{\text{n}}$, $\text{n}\ge 1$, to be the mean of ${\text{D}}_{\text{n,1}},\dots ,{\text{D}}_{\text{n,n}}$. We show that E$[{\text{D}}_{\text{n}}]$ is a monotonically increasing function of n and is bounded by $\ln$ n. We apply these results to a practical application involving a video-on-demand system with interleaved movie files and a delayed start protocol for keeping a balanced workload.

The exact values of $c(n)$ are determined, where $c(n)$ denotes the largest $k$ for which there exists a triangle-free $k$-regular graph on $n$ vertices containing a cut-vertex. As a corollary, we obtain a lower bound on the densest triangle-free regular graphs of given order that do not have a one-factorization.

In the search for doubly resolvable Kirkman triple systems of order $v$, systems admitting an automorphism of order $(v-3)/3$ fixing three elements, and acting on the remaining elements in three orbits of length $(v-3)/3$, have been of particular interest. We have established by computer that 100 such Kirkman triple systems exist for $v=21$, 90,598 for $v=27$, at least 4,494,390 for $v=33$, and at least 1,626,684 for $v=39$. This improves substantially on known lower bounds for numbers of Kirkman triple systems. We also establish that the KTS(27)s so produced yield 47 nonisomorphic doubly resolved KTS(27)s admitting the same automorphism.