The vertices of the queen’s graph \(Q_n\) are the squares of an \(n \times n\) chessboard and two squares are adjacent if a queen placed on one covers the other. Informally, a set \(I\) of queens on the board is irredundant if each queen in \(I\) covers a square (perhaps its own) which is not covered by any other queen in \(I\). It is shown that the cardinality of any irredundant set of vertices of \(Q_n\) is at most \(\left\lfloor {6n+6-8}\sqrt{n+3} \right\rfloor\) for \(n \geq 6\). We also show that the bound is not exact since \(\mathrm{IR}(Q_8) \leq 23\).

The star graph \(S_n\) is a graph with \(S_n\), the set of all permutations over \(\{1, \ldots, n\}\) as its vertex set; two vertices \(\pi_1\) and \(\pi_2\) are connected if \(\pi_1\) can be obtained from \(\pi_2\) by swapping the first element of \(\pi_2\) with one of the other \(n-1\) elements. In this paper we establish the genus of the star graph. We show that the genus, \(g_n\) of \(S_n\) is exactly equal to \(n!(n-4)/6+1\) by establishing a lower bound and inductively giving a drawing on a surface of appropriate genus.

In this note, a conjecture of P. Johnson Jr. on the Hall condition number is disproved.

Each vertex of a graph \(G = (V, E)\) is said to dominate every vertex in its closed neighborhood. A set \(S \subseteq V\) is a double dominating set for \(G\) if each vertex in \(V\) is dominated by at least two vertices in \(S\). The smallest cardinality of a double dominating set is called the double domination number \(dd(G)\). We initiate the study of double domination in graphs and present bounds and some exact values for \(dd(G)\). Also, relationships between \(dd(G)\) and other domination parameters are explored. Then we extend many results of double domination to multiple domination.

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].