This paper is about critical sets in Latin squares and the weaker concept of partial Latin squares with unique completion. This work involves taking two known partial Latin squares with unique completion, or critical sets in Latin squares, and using a product construction to produce new partial Latin squares with unique completion, or new critical sets in larger Latin squares.

In this paper, we prove the following result:
Let \(D\) be a disconnected oriented graph of order \(n\). If
\(d^+(u)+d^+(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^+(u) \cap N^+(v) \neq \emptyset\) and \(d^-(u) + d^-(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^-(u) \cap N^-(v) \neq \emptyset\), then \(D\) contains a directed Hamiltonian cycle.

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we discuss the relationship between the vertex-neighbor-integrity and some well-known graphic parameters.

We construct, for all positive integers \(u\) and \(v\) with \(u \leq v\), a decomposition of \(K_v – K_u\) (the complete graph on \(v\) vertices with a hole of size \(u\)) into the maximum possible number of edge-disjoint triangles.

In this paper, we deal with the convex generators of a graph \(G = (V(G), E(G))\). A convex generator being a minimal set whose convex hull is \(V(G)\), we show that it is included in the “boundary” of \(G\). Then we show that the “boundary” of a polymino’s graph, or more precisely the seaweed’s “boundary”, enjoys some nice properties which permit us to prove that for such a graph \(G\), the minimal size of a convex generator is equal to the maximal number of hanging vertices of a tree \(T\), obtained from \(G\) by a sequence of generator-preserving contractions.

We address questions of Chartrand et al. about \(k\)-stratified graphs and distance graphs. A \(k\)-stratified graph \(G\) is a graph whose vertices have been partitioned into \(k\) distinct color classes, or strata. An underlying graph \(G’\) is obtained by ignoring the colors of \(G\). We prove that for every pair of positive integers \(k\) and \(l\), there exists a pair of \(2\)-stratified graphs with exactly \(k\) greatest common stratified subgraphs such that their underlying graphs have exactly \(l\) greatest common subgraphs.

A distance graph \(D(A)\) has vertices from some set \(A\) of \(0-1\) sequences of a fixed length and fixed weight. Two vertices are adjacent if one of the corresponding sequences can be obtained from the other by the interchange of a \(0\) and \(1\). If \(G\) is a graph of order \(m\) that can be realized as the distance graph of \(0-1\) sequences, then we prove that the \(0-1\) sequences require length at most \(2m-2\). We present a list of minimal forbidden induced subgraphs of distance graphs of \(0-1\) sequences.

A distance graph \(D(G)\) has vertices from some set \(G\) of graphs or \(k\)-stratified graphs. Two vertices are adjacent if one of the corresponding graphs can be obtained from the other by a single edge rotation. We prove that \(K_n\) minus an edge is a distance graph of a set of graphs. We fully characterize which radius one graphs are distance graphs of \(0-1\) sequences and which are distance graphs of graphs with distinctly labelled vertices.

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

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.

The existence of holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) of types \(h^n\) and \(1^{n}u^1\) is investigated. For type \(h^n\), new pairs of \((h, n)\) are constructed so that the possible exceptions of \((h, n)\) for the existence of such HSOLSSOMs are reduced to \(11\) in number. Two necessary conditions for the existence of HSOLSSOMs of type \(1^{n}u^1\) are (1) \(n \geq 3u + 1\) and (2) \(n\) must be even and \(u\) odd. Such an HSOLSSOM gives rise to an incomplete SOLSSOM. For \(3 \leq u \leq 15\), the necessary conditions are shown to be sufficient with seven possible exceptions. It is also proved that such an HSOLSSOM exists whenever even \(n \geq 5u + 9\) and odd \(u \leq 9\).

We prove: A connected magic graph with \(n\) vertices and \(q\) edges exists if and only if \(n = 2\) and \(q = 1\) or \(n \geq 5\) and \(\frac{5n}{4} < q < \frac{n(n-1)}{2} \).

Sharp bounds are presented for the \(\lambda\)-number of the Cartesian product of a cycle and a path, and of the Cartesian product of two cycles.

A set \(S = \{v_1, v_2, \ldots, v_n\}\) of vertices in a graph \(G\) with associated sequence \(k_1, k_2, \ldots, k_n\) of nonnegative integers is called a step domination set if every vertex of \(G\) is at distance \(k_i\) from \(v_i\) for exactly one \(i\) (\(1 \leq i \leq n\)). The minimum cardinality of a step domination set is called the step domination number of \(G\). This parameter is determined for several classes of graphs and is investigated for trees.

We completely determine the spectrum (i.e. set of orders) of complete \(4\)-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete \(4\)-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter \(5\). As regards the remaining possible finite diameters, \(2, 3, 4\), we present partial results, focusing on decompositions of \(K_{n,n,n,m}\) and \(K_{n,n,m,m}\) for odd \(m\) and \(n\).

In this paper we determine the \(k\)-domination numbers of the cardinal products \(P_2 \times P_n, \ldots, P_{2k+1} \times P_n\) for all integers \(k \geq 2, n \geq 3\).

In this paper we investigate the nature of both the \(2\)-packing number and the minimum domination number of the cartesian product of graphs where at least one of them has the property that every vertex is either a leaf or has at least one leaf as a neighbour.

Let \(H\) be a graph, and let \(k\) be a positive integer. A graph \(G\) is \(H\)-coverable with overlap \(k\) if there is a covering of all the edges of \(G\) by copies of \(H\) such that no edge of \(G\) is covered more than \(k\) times. The number \(ol(H, G)\) is the minimum \(k\) for which \(G\) is \(H\)-coverable with overlap \(k\).

It is established (Theorem 2.1) that if \(n\) is sufficiently large then
\[ol(H, K_n) \leq 2.\]

For \(H\) being a path, a matching or a star it is enough to assume \(|H| \leq n\) (Theorem 3.1).

The same result is obtained (Main Theorem) for any graph \(H\) having at most four vertices, or else at most four edges with a single exception \(ol(K_4, K_5) = 3\).