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.

The (previously studied) notions of secure domination and of weak Roman domination involve the construction of protection strategies in a simple graph \( G = (V, E) \), by utilizing the minimum number of guards needed at vertices in \( V \) to protect \( G \) in different scenarios (these minimum numbers are called the secure [weak Roman] domination parameters for the graph). In this paper, these notions are generalized in the sense that safe configurations in \( G \) are not merely sought after one move, but rather after each of \( k \geq 1 \) moves. Some general properties of these generalized domination parameters are established, after which the parameter values are found for certain simple graph structures (such as paths, cycles, multipartite graphs, and products of complete graphs, cycles, and paths).

We establish necessary and sufficient conditions on \( m \) and \( n \) for \( K_m \times K_n \), the Cartesian product of two complete graphs, to be decomposable into cycles of length \( 8 \). We also provide a complete classification of the leaves that are possible with maximum packings of complete graphs with \( 8 \)-cycles.

We consider the rank of the adjacency matrix of the line graph for some classes of regular graphs. In particular, we study the line graphs of cycles, paths, complete graphs, complete bipartite and multipartite graphs, circulant graphs of degrees three and four, and some Cartesian graph products.

For each vertex \( v \) in a graph \( G \), let there be associated a particular type of a subgraph \( F_v \) of \( G \). In this context, the vertex \( v \) is said to dominate \( F_v \). A set \( S \) of vertices of \( G \) is called a full dominating set if every vertex of \( G \) belongs to a subgraph \( F_v \) of \( G \) for some \( v \in S \) and every edge of \( G \) belongs to a subgraph \( F_w \) of \( G \) for some \( w \in S \). The minimum cardinality of a full dominating set of \( G \) is its full domination number \( \gamma_F(G) \). A full dominating set of \( G \) of cardinality \( \gamma_F(G) \) is called a \( \gamma_F \)-set of \( G \).

We study three types of full domination in graphs: full star domination, where \( F_v \) is the maximum star centered at \( v \); full closed domination, where \( F_v \) is the subgraph induced by the closed neighborhood of \( v \); and full open domination, where \( F_v \) is the subgraph induced by the open neighborhood of \( v \).

A subset \( T \) of a \( \gamma_F \)-set \( S \) in a graph \( G \) is a forcing subset for \( S \) if \( S \) is the unique \( \gamma_F \)-set containing \( T \). The forcing full domination number of \( S \) in \( G \) is the minimum cardinality of a forcing subset for \( S \), and the forcing full domination number \( f_{\gamma_F}(G) \) of the graph \( G \) is the minimum forcing full domination number among all \( \gamma_F \)-sets of \( G \).

We present several realization results concerning forcing parameters in full domination.

A minimum feedback arc set of a digraph is a smallest sized set of arcs whose reversal makes the resulting digraph acyclic. Given an acyclic digraph \( D \), we seek a smallest sized tournament \( T \) having \( A(D) \) as a minimum feedback arc set. The reversing number of a digraph \( D \) equals \( |V(T)| – |V(D)| \). We investigate the reversing number of the \( k \)th power of directed Hamiltonian path \( P_n^k \), when \( k \) is fixed and \( n \) tends to infinity. We show that even for small values of \( k \), where \( |A(P_n^k)| \) is much closer to \( |A(P_n)| \) than \( |A(T_n)| \), the opposite relationship holds for the reversing number.