A graph \(G\) is said to be \({hypohamiltonian}\) if \(G\) is not Hamiltonian but for each \(v \in V(G)\), the vertex-deleted subgraph \(G – v\) is Hamiltonian. In this paper, we show that there is no hypohamiltonian graph on \(17\) vertices and thereby complete the answer to the question, “For which values of \(n\) do there exist hypohamiltonian graphs on \(n\) vertices?”. In addition, we present an exhaustive list of hypohamiltonian graphs on fewer than \(18\) vertices and extend previously obtained results for cubic hypohamiltonian graphs.

We consider the problem of constructing pairwise balanced designs of order \(v\) with a hole of size \(k\). This problem was addressed by Hartman and Heinrich who gave an almost complete solution. To date, there remain fifteen unresolved cases. In this paper, we construct designs settling all of these.

All non-Hamiltonian cubic \(2\)-edge-connected graphs, including all snarks, on \(16\) or fewer vertices are listed, along with some of their properties. Questions concerning the existence of graphs with certain properties are posed.

We deal with finite graphs which admit a labeling of edges by pairwise different positive integers from the set \(\{1, 2, \ldots, |E(G)|\}\) in such a way that the sum of the labels of the edges incident to a particular vertex is the same for all vertices. We construct edge labelings for two families of quartic graphs, i.e., regular graphs of degree \(d = 4\).

Kibler, Baumert, Lander, and Kopilovich (cf. [7], [1], [10], and [8] respectively), studied the existence of \( (v, k, \lambda) \)-abelian difference sets with \( k \leq 100 \). In Lander and Kopilovich’s works, there were \( 13 \) and \( 8 \) \( (v, k, \lambda) \) tuples, respectively, in which the problem was open. Later, several authors have completed these studies and nowadays the problem is open for \( 6 \) and \( 7 \) tuples, respectively. Jungnickel (cf. [9]) lists some unsolved problems on difference sets. One of them is to extend Lander’s table somewhat. By following this idea, this paper deals with the existence or non-existence of \( (v, k, \lambda) \)-abelian difference sets with \( 100 < k \leq 150 \). There exist \( 277 \) tuples that satisfy the basic relationship between the parameters \( v \), \( k \), and \( \lambda \), \( k \leq v/2 \), Schutzenberger and Bruck-Chowla-Ryser's necessary conditions, and \( 100 < k \leq 150 \). In order to reduce this number, we have written in C several programs which implement some known criteria on non-existence of difference sets. We conclude that the only \( (v, k, \lambda) \) tuples, with \( 100 < k \leq 150 \), for which a difference set in some abelian group of order \( v \) can exist are \begin{align*} &(10303, 102, 1), (10713, 104, 1), (211, 105, 52), (11557, 108, 1), \\ &(223, 111, 55), (11991, 110, 1), (227, 113, 56), (12883, 114, 1), \\ &(378, 117, 386), (239, 119, 59), (256, 120, 56), (364, 121, 40), \\ &(243, 121, 60), (14763, 122, 1), (251, 125, 62), (15751, 126, 1), \\ &(351, 126, 45), (255, 127, 63), (16257, 128, 1), (16513, 129, 1), \\ &(263, 131, 65), (17293, 132, 1), (1573, 132, 11), (1464, 133, 12), \\ &(271, 135, 67), (18907, 138, 1), (19461, 140, 1), (283, 141, 70), \\ &(22351, 150, 1), (261, 105, 42), (429, 198, 27), (1200, 110, 10), \\ &(768, 118, 18), (841, 120, 17), (715, 120, 20), (5085, 124, 3), \\ &(837, 133, 21), (419, 133, 42), (1225, 136, 15), (361, 136, 51), \\ &(1975, 141, 10), (1161, 145, 18), (465, 145, 45), (5440, 148, 4), \\ &(448, 150, 50). \end{align*} It is known that there exist difference sets for the first \( 29 \) tuples and the problem is open for the remaining \( 16 \). Besides, in Table 1, we give the criterion that we have applied to determine the non-existence of \( (v, k, \lambda) \)-difference sets for the rest of the tuples.

It is shown how any integral monoid can be represented as the projection of the intersection of the solution set of a finite collection of linear inequalities, and a lattice, both in a possibly higher dimension. This in turn can be used to derive a known representation using Chvátal functions, in the same dimension as the monoid. Both representations can be regarded as discrete analogues of the classical theorems of Weyl and Minkowski, but applicable in non-polyhedral monoids.

Both the bandwidth and additive bandwidth of a graph supply information about the storage requirements of a representation of the graph. In particular, the bandwidth measures how far \(1\)’s must be from the main diagonal of the graph’s adjacency matrix, while the additive bandwidth yields the same information with respect to the main contradiagonal. Thus, storage can be significantly reduced from that required by the full adjacency matrix if at least one of the two types of bandwidths is small, which is most likely to occur for sparse matrices. Alternatively, one could store a representation of the complement of the graph if one of its two bandwidths is small. We relate the additive bandwidth to other graphical invariants and then concentrate on Nordhaus-Gaddum type results to show that there are graphs for which both the bandwidth and the additive bandwidth of both the graph and its complement are large. In other words, some graphs require near maximum storage.

A star-factor of a graph \(G\) is a spanning subgraph of \(G\) such that each component of which is a star. In this paper, we study the structure of the graphs with a unique star-factor and obtain an upper bound on the mnumber of edges such graphs can have. We also investigate the number of star-factors in a regular graph.

Let \(J[v]\) denote the set of numbers \(k\) such that there exist two semi-symmetric Latin squares (SSLS) of order \(v\) which have \(k\) entries in common. In this paper, we show that \begin{align*}
J[3] &= \{0, 9\}, J[4] = \{0, 1, 3, 4, 9, 12, 16\}, \\
J[5] &= \{0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 18, 21, 25\}, \\
J[6] &= \{0, 1, 2, \ldots, 23, 24, 26, 27, 28, 29, 32, 36\}, \text{ and} \\
J[v] &= \{0, 1, 2, \ldots, v^2\} \setminus \{v^2-1, v^2-2, v^2-3, v^2-5, v^2-6\}
\end{align*}
for each \(v \geq 7\).

A holey perfect Mendelsohn design of type \(h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k}\) (HPMD\((h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k})\)), with block size four is equivalent to a frame idempotent quasigroup satisfying Stein’s third law with the same type, where a frame quasigroup of type \(h_1^{n_1} h_2^{n_2} \ldots h_k^{n_k}\) means a quasigroup of order \(n\) with \(n_i\) missing subquasigroups (holes) of order \(h_i\), \(1 \leq i \leq k\), which are disjoint and spanning, that is \(\sum_{1\leq i \leq k} n_ih_i = n\). In this paper, we investigate the existence of HPMD\((2^n3^1)\) and show that an HPMD\((2^n3^1)\) exists if and only if \(n \geq 4\). As an application, we readily obtain HSOLS\((2^n3^1)\) and establish the existence of \((2,3,1)\) [or \((3,1,2)\)]-HCOLS\((2^n3^1)\) for all \(n \geq 4\).