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.