We investigate the following problem: given a set \(S \subset \mathbb{R}^2\) in general position and a positive integer \(k\), find a family of matchings \(\{M_1, M_2, \ldots, M_k\}\) determined by \(S\) such that if \(i \neq j\) then each segment in \(M_i\) crosses each segment in \(M_j\). We give improved linear lower bounds on the size of the matchings in such a family.

In this paper, we improve the upper bounds for the genus of the group \(\mathcal{A} = {Z}_{m_1} \times {Z}_{m_2} \times {Z}_{m_3}\) (in canonical form) with at least one even \(m_i\), \(i = 1, 2, 3\). As a special case, our results reproduce the known results in the cases \(m_3 = 3\) or both \(m_2\) and \(m_3\) are equal to \(3\).

Given a good drawing of a graph on some orientable surface, there exists a good drawing of the same graph with one more or one less crossing on an orientable surface which can be exactly determined. Our methods use a new combinatorial representation for drawings. These results lead to bounds related to the Thrackle Conjecture.

The minimum number of incomplete blocks required to cover, exactly \(\lambda\) times, all \(t\)-element subsets from a set \(V\) of cardinality \(v\) (\(v > t\)) is denoted by \(g(\lambda, t; v)\). The value of \(g(2, 2; v)\) is known for \(v = 3, 4, \ldots, 11\). It was previously known that \(13 \leq g(2, 2; 12) \leq 16\). We prove that \(g(2, 2; 12) \geq 14\).

In [8] a graph representation of the Fibonacci numbers \(F_n\) and Lucas numbers \(F_y^*\) was presented. It is interesting to know that they are the total numbers of all stable sets of undirected graphs \(P_n\) and \(C_n\), respectively. In this paper we discuss a more general concept of stable sets and kernels of graphs. Our aim is to determine the total numbers of all \(k\)-stable sets and \((k, k-1)\)-kernels of graphs \(P_n\) and \(C_n\). The results are given by the second-order linear recurrence relations containing generalized Fibonacci and Lucas numbers. Recent problems were investigated in [9], [10].

We give a constructive and very simple proof of a theorem by Chech and Colbourn [7] stating the existence of a cyclic \((4p, 4, 1)\)-BIBD (i.e. regular over \({Z}_{4p}\)) for any prime \(p \equiv 13 \mod 24\). We extend the theorem to primes \(p \equiv 1 \mod 24\) although in this case the construction is not explicit. Anyway, for all these primes \(p\), we explicitly construct a regular \((4p, 4, 1)\)-BIBD over \({Z}_{2}^{2} \oplus {Z}_p\).

In this paper, we prove the gracefulness of a new class of graphs denoted by \(K_{n}\otimes S_{2^{{n-1}}-\binom{n}{2}}\).
We also prove that the graphs consisting of \(2m + 1\) internally disjoint paths of length \(2r\) each, connecting two fixed vertices, are also graceful.

Erdős and Sésg conjectured in 1963 that if \(G\) is a graph of order \(p\) and size \(q\) with \(q > \frac{1}{2}p(k-1)\), then \(G\) contains every tree of size \(k\). This is proved in this paper when the girth of the complement of \(G\) is greater than \(4\).

Using path counting arguments, we prove
\(min\{\binom{x_1+x_2+y_1+y_2}{x_1,x_2,(y_1+y_2)},\binom{(x_1+x_2+y_1+y_2)}{(x_1+x_2),y_1,y_2}\}\leq\binom{x_1+y_1}{x_1}\binom{x_1+y_2}{x_1}\binom{x_2+y_1}{x_2}\binom{x_2+y_2}{x_2}\)

This inequality, motivated by graph coloring considerations, has an interesting geometric interpretation.