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.