We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs \( G_{m,n} \). The bound is within \( 5 \) of a known upper bound that has been conjectured to be the exact domination number of the complete grid graphs.

A large set of KTS(\(v\)), denoted by LKTS(\(v\)), is a collection of (\(v-2\)) pairwise disjoint KTS(\(v\)) on the same set. In this paper, it is proved that there exists an LKTS(\(3^n \cdot 91\)) for any integer \(n \geq 1\).

If \( x \) is a vertex of a digraph \( D \), then we denote by \( d^+(x) \) and \( d^-(x) \) the outdegree and the indegree of \( x \), respectively. The global irregularity of a digraph \( D \) is defined by \(i_g(D) = \max\{d^+(x), d^-(x)\} – \min\{d^+(y), d^-(y)\}\) over all vertices \( x \) and \( y \) of \( D \) (including \( x = y \)). If \( i_g(D) = 0 \), then \( D \) is regular, and if \( i_g(D) \leq 1 \), then \( D \) is called almost regular. The local irregularity is defined as \(i_l(D) = \max[|d^+(x) – d^-(x)|]\) over all vertices \( x \) of \( D \). The path covering number of \( D \) is the minimum number of directed paths in \( D \) that are pairwise vertex disjoint and cover the vertices of \( D \). A semicomplete \( c \)-partite digraph is a digraph obtained from a complete \( c \)-partite graph by replacing each edge with an arc, or a pair of mutually opposite arcs with the same end vertices. If a semicomplete \( c \)-partite digraph \( D \) does not contain an oriented cycle of length two, then \( D \) is called a \( c \)-partite tournament.
In 2000, Gutin and Yeo [7] proved sufficient conditions for the local irregularity of a semicomplete multipartite digraph to secure a path covering number of at most \( k \). In this paper, we will give a useful supplement to this result by using bounds for the global irregularity that guarantee a path covering number of at most \( k \). As an application, we will present sufficient conditions for close to regular multipartite tournaments containing a Hamiltonian path. Especially, we will characterize almost regular \( c \)-partite tournaments containing a Hamiltonian path.

An extended \(7\)-cycle system of order \( n \) is an ordered pair \( (V, B) \), where \( B \) is a collection of edge-disjoint 7-cycles, 3-tadpoles, and loops which partition the edges of the graph \( K_n^+ \) whose vertex set is an \( n \)-set \( V \). In this paper, we show that an extended 7-cycle system of order \( n \) exists for all \( n \) except \( n = 2, 3, \) and \( 5 \).

A grid graph is a finite induced subgraph of the infinite 2-dimensional grid defined by \( \mathbb{Z} \times \mathbb{Z} \) and all edges between pairs of vertices from \( \mathbb{Z} \times \mathbb{Z} \) at Euclidean distance precisely \( 1 \). An \( m \times n \)-rectangular grid graph is induced by all vertices with coordinates from \( 1 \) to \( m \) and from \( 1 \) to \( n \), respectively. A natural drawing of a (rectangular) grid graph \( G \) is obtained by drawing its vertices in \( \mathbb{R}^2 \) according to their coordinates. We consider a subclass of the rectangular grid graphs obtained by deleting some vertices from the corners. Apart from the outer face, all (inner) faces of these graphs have area one (bounded by a \( 4 \)-cycle) in a natural drawing of these graphs. We determine which of these graphs contain a Hamilton cycle, i.e., a cycle containing all vertices, and solve the problem of determining a spanning \( 2 \)-connected subgraph with as few edges as possible for all these graphs.