In this paper, we show that group divisible designs with block size five, group-type and index odd exist with a few possible exceptions.

A digraph $D$ is called semicomplete $c$-partite if its vertex set $V(D)$ can be partitioned into $c$ sets (partite sets) such that for any two vertices $x$ and $y$ in different partite sets, at least one arc between $x$ and $y$ is in $D$ and there are no arcs between vertices in the same partite set. The path covering number of $D$ is the minimum number of paths in $D$ that are pairwise vertex disjoint and cover the vertices of $D$. Volkmann (1996) has proved two sufficient conditions on hamiltonian paths in semicomplete multipartite digraphs and conjectured two related sufficient conditions. In this paper, we derive sufficient conditions for a semicomplete multipartite digraph to have path covering number at most $k$ and show that Volkmann’s results and conjectures can be readily obtained from our conditions.

The Fibonacci number of a graph is the number of independent sets of the graph. In this paper, we compute algorithmically the Fibonacci numbers of lattice product graphs.

In this note, we solve a conjecture of Dénes, Mullen, and Suchower [2] on power sets of Latin squares.

In this article, we construct a large set of idempotent quasigroups of order 62. The spectrum for large sets of idempotent quasigroups of order $n$ (briefly, $LQ(n)$) is the set of all integers $n\ge 3$ with the exception $n=6$ and the possible exception $n=14$.

We settle the existence status of some previously open cases of abelian difference sets. Our results fill ten missing entries in the recent table of Lepez and Sanchez, all with answer `No’.

Recently, Raines and Rodger have proved that for all $\lambda \ge 1$, any partial extended triple system of order $n$ and index $\lambda$ can be embedded in a (complete) extended triple system of order $v$ and index $\lambda$ for any even $v\ge 4n+6$. In this note, it is shown that if $\lambda$ is even then this bound on $v$ can be improved to all $v\ge 3n+5$, and under some conditions to all $v\ge 2n+1$.

It is shown that if a graph $G$ is connected, claw-free, and such that the vertices of degree 1 of every induced bull have a common neighbor in $G$, then $G$ is traceable.

Some extremal set problems can be phrased as follows. Given an $m\times n$ $(0,1)$-matrix $A$ with no repeated columns and with no submatrix of a certain type, what is a bound on $n$ in terms of $m$? We examine a conjecture of Frankl, Füredi, and Pach and the author that when we forbid a $k\times l$ submatrix $F$ then $n$ is $O(m^k)$. Two proof techniques are presented, one is amortized complexity and the other uses a result of Alon to show that $n$ is $O(m^{2k-1-ϵ})$ for $ϵ=(k-1)/(13{\log }_{2}l)$, improving on the previous bound of $O(m^{2k-1})$.

A graph $H$ is $G$-decomposable if $H$ can be decomposed into subgraphs, each of which is isomorphic to $G$. A graph $G$ is a greatest common divisor of two graphs $G_1$ and $G_2$ if $G$ is a graph of maximum size such that both $G_1$ and $G_2$ are $G$-decomposable. The greatest common divisor index of a graph $G$ of size $q$ is the greatest positive integer $n$ for which there exist graphs $G_1$ and $G_2$, both of size at least $nq$, such that $G$ is the unique greatest common divisor of $G_1$ and $G_2$. The corresponding concepts are defined for digraphs. Relationships between greatest common divisor index for a digraph and for its underlying graph are studied. Several digraphs are shown to have infinite index, including matchings, short paths, union of stars, transitive tournaments, the oriented 4-cycle. It is shown that for $5\le p\le 10$, if a graph $F$ of sufficiently large size is $C_p$-decomposable, then $F$ is also $(P_{p-1}\cup P_3)$-decomposable. From this it follows that the even cycles $C_6$, $C_8$ and $C_{10}$ have finite greatest common divisor index.

A chess-like game board called a hive, consisting of hexagonal cells, and a board piece called a queen are defined. For queens on hexagonally shaped hives, values are obtained for the lower and independent domination numbers, the upper independence number and the diagonal domination number, as well as a lower bound for the upper domination number. The concept of a double column placement is introduced.

Two vertices in a graph $H$ are said to be pseudosimilar if $H–u$ and $H–v$ are isomorphic but no automorphism of $H$ maps $u$ into $v$. Pseudosimilar edges are analogously defined. Graphs in which every vertex is pseudosimilar to some other vertex have been known to exist since 1981. Producing graphs in which every edge is pseudosimilar to some other edge proved to be more difficult. We here look at two constructions of such graphs, one from $\frac{1}{2}$-transitive graphs and another from edge-transitive but not vertex-transitive graphs. Some related questions on Cayley line-graphs are also discussed.

The maximum cardinality of a partition of the vertex set of a graph $G$ into dominating sets is the domatic number of $G$, denoted $d(G)$. The codomatic number of $G$ is the domatic number of its complement, written $d(\overline{G})$. We show that the codomatic number for any cubic graph $G$ of order $n$ is $n/2$, unless $G\in \{K_4,G_1\}$ where $G_1$ is obtained from $K_{2,3}\cup K_3$ by adding the edges of a 1-factor between $K_3$ and the larger partite set of $K_{2,3}$.

Various connections have been established between the permanent and the determinant of the adjacency matrix of a graph. Connections are also made between these scalars and the number of perfect matchings in a graph. We establish conditions for graphs to have determinant 0 or $\pm 1$. Necessary conditions and sufficient conditions are obtained for graphs to have permanent equal to 0 or to 1.

Let $h\ge 1$. For each admissible $v$, we exhibit a nested balanced path design $H(v,2h+1,1)$. For each admissible odd $v$, we exhibit a nested balanced path design $H(v,2h,1)$. For every $v\equiv 4(\mathrm{mod}6)$, $v\ge 10$, we exhibit a nested balanced path design $H(v,4,1)$ except possibly if $v\in \{16,52,70\}$.

For each $v\equiv 0(\mathrm{mod}4h)$, $v\ge 4h$, we exhibit a nested path design $P(v,2h+1,1)$. For each $v\equiv 0(\mathrm{mod}4h-2)$, $v\ge 4h-2$, we exhibit a nested path design $P(v,2h,1)$. For every $v\equiv 3(\mathrm{mod}6)$, $v\ge 9$, we exhibit a nested path design $P(v,4,1)$ except possibly if $v=39$.

A sequence of positive integers $a_1\le a_2\le \dots \le a_n$ is called an ascending monotone wave of length $n$, if $a_{i+1}–a_i\ge a_i–a_{i-1}$ for $i=2,\dots ,n-1$. If $a_{i+1}–a_i>a_i–a_{i-1}$ for all $i=2,\dots ,n-1$ the sequence is called an ascending strong monotone wave of length $n$. Let $Z_k$ denote the cyclic group of order $k$. If $k|n$, then we define $MW(n,Z_k)$ as the least integer $m$ such that for any coloring $f:\{1,\dots ,m\}\to Z_k$, there exists an ascending monotone wave of length $n$, where $a_n\le m$, such that $\sum _{i=1}^{n}f(a_i)=0\mathrm{mod}k$. Similarly, define $SMW(n,Z_k)$, where the ascending monotone wave in $MW(n,Z_k)$ is replaced by an ascending strong monotone wave. The main results of this paper are:

1. $\frac{\sqrt{k}}{2}n\le MW(n,Z_k)\le c_1(k)n$. Hence, this result is tight up to a constant factor which depends only on $k$.
2. $(\genfrac{}{}{0ex}{}{n}{2})<SMW(n,Z_k)\le c_2(k)n^2$. Hence, this result is tight up to a constant factor which depends only on $k$.
3. $MW(n,Z_2)=3n/2$.
4. $\frac{23}{12}n–7/6\le MW(n,Z_3)\le 2n+3$.

These results are the zero-sum analogs of theorems proved in [1] and [5].

For $\omega \le 33$, the known necessary conditions for existence of a $(\nu ,\{5,{\omega }^{\ast }\},1)$ PBD, namely $\nu ,\omega \equiv 1\mathrm{mod}4$, $\nu \ge 4\omega +1$ and $\nu \equiv \omega$ or $4\omega +1\mathrm{mod}20$ are known to be sufficient in all but 26 cases. This paper provides several direct constructions which reduce the number of exceptions to 8.

The question whether every connected graph $G$ has a spanning tree $T$ of minimum average distance such that $T$ is distance preserving from some vertex is answered in the negative. Moreover, it is shown that, if such a tree exists, it is not necessarily distance preserving from a median vertex.

In this note, we investigate three versions of the overfull property for graphs and their relation to the edge-coloring problem. Each of these properties implies that the graph cannot be edge-colored with $\mathrm{\Delta }$ colors, where $\mathrm{\Delta }$ is the maximum degree. The three versions are not equivalent for general graphs. However, we show that some equivalences hold for the classes of indifference graphs, split graphs, and complete multipartite graphs.

Let $K_n$ be the complete graph on $n$ vertices. Let $I(X)$ denote the set of integers $k$ for which a pair of maximum pentagon packings of graph $X$ exist having $k$ common 5-cycles. Let $J(n)$ denote the set $\{0,1,2,\dots ,P-2,P\}$, where $P$ is the number of 5-cycles in a maximum pentagon packing of $K_n$. This paper shows that $I(K_n)=J(n)$, for all $n\ge 1$.

It is shown that the Overfull Conjecture, which would provide a chromatic index characterization for a large class of graphs, and the Conformability Conjecture, which would provide a total chromatic number characterization for a large class of graphs, both in fact apply to almost all graphs, whether labelled or unlabelled. The arguments are based on Polya’s theorem, and are elementary in the sense that practically no knowledge of random graph theory is presupposed. It is similarly shown that the Biconformability Conjecture, which would provide a total chromatic number characterization for a large class of equibipartite graphs, in fact applies to almost all equibipartite graphs.

The $[0,\mathrm{\infty })$-valued dominating function minimization problem has the $[0,\mathrm{\infty })$-valued packing function as its linear programming dual. The standard $\{0,1\}$-valued minimum dominating set problem has the $\{0,1\}$-valued maximum packing set problem as its binary dual. The recently introduced complementary problem to a minimization problem is also a maximization problem, and the complementary problem to domination is the maximum enclaveless problem. This paper investigates the dual of the enclaveless problem, namely, the domination-coverage number of a graph. Specifically, let $\eta (G)$ denote the minimum total coverage of a dominating set. The number of edges covered by a vertex $v$ equals its degree, $\mathrm{deg}v$, so $\eta (G)=\text{MIN}\{\sum _{s\in S}\mathrm{deg}s:S\text{ is a dominating set}\}$. Bounds on $\eta (G)$ and computational complexity results are presented.

In this note, we computationally prove that the size of smallest critical sets for the quaternion group of order eight, the group ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$ and the dihedral group of order eight are 20, 21 and 22, respectively.

A graph is said $h$-decomposable if its edge-set is decomposable into hamiltonian cycles. In this paper, we prove that if $G=L_1\cup L_2\cup L_3$ is a strongly hamiltonian bipartite cubic graph (where $L_i$ is a perfect matching, for $1\le i\le 3$ and $(L_1,L_2,L_3)$ is a $1$-factorization of $G$), then $G\times C_{2n+1}$ (where $n$ is odd and $n\ge 1$) is decomposable. As a corollary, we show that for $r\ge 1$ odd and $n\ge 3$, $K_{r,r}\times K_n$ is $h$-decomposable. Moreover, in the case where $G$ is a strongly hamiltonian non-bipartite cubic graph, we prove that the same result can be derived using a special perfect matching. Hence $K_{2r}\times K_{2n+1}$ will be $h$-decomposable, for $r,n\ge 1$.

To study the product of $G=L_1\cup L_2\cup L_3$ by even cycle, we define a dual graph $G_C$ based on an alternating cycle subset of $L_2\cup L_3$. We show that if a non-bipartite cubic graph $G=L_1\cup L_2\cup L_3$, with $|V(G)|=2m$, admits $L_1\cup L_2$ as a hamiltonian cycle and $G_C$ is connected, then $G\times K_2$ is hamiltonian and $G\times C_{2n}$ has two edge-disjoint hamiltonian cycles. Finally, we prove that if $C=L_2\cup L_3$ and $L_1\cup L_3$ admits a particular alternating $4$-cycle $C^{\prime }$, then $G\times C_{2n}$ is $h$-decomposable.