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.

A union closed (UC) family \( \mathcal{A} \) is a finite family of sets such that the union of any two sets in \( \mathcal{A} \) is also in \( \mathcal{A} \). Peter Frankl conjectured in 1979 that for every union closed family \( \mathcal{A} \), there exists some \( x \) contained in at least half the members of \( \mathcal{A} \). In this paper, we show that if a UC family \( \mathcal{A} \) fails the conjecture, then no element can appear in more than two of its \( 3 \)-sets, and so the number of \( 3 \)-sets in \( \mathcal{A} \) can be no more than \( \frac{2n}{3} \).

A \( (k,d) \)-total coloring (\( k,d \in \mathbb{N}, k \geq 2d \)) of a graph \( G \) is an assignment \( c \) of colors \( \{0,1,\ldots,k-1\} \) to the vertices and edges of \( G \) such that \( d \leq |c(x_i) – c(x_j)| \leq k – d \) whenever \( x_i \) and \( x_j \) are two adjacent edges, two adjacent vertices, or an edge incident to a vertex. The circular total chromatic number \( \chi_c”(G) \) is defined by \(\chi_c”(G) = \inf\{k/d : G \text{ has a } (k, d)\text{-total coloring}\}.\) It was proved that \( \chi”(G) – 1 < \chi_c''(G) \leq \chi''(G) \) — where \( \chi''(G) \) is the total chromatic number of \( G \) — with equality for all type-1 graphs and most of the so far considered type-2 graphs. We determine an infinite class of graphs \( G \) such that \( \chi_c''(G) < \chi''(G) \) and we list all graphs of order \( <7 \) with this property.

In this paper we consider a variation of the classical Turán-type extremal problems. Let \( S \) be an \( n \)-term graphical sequence, and \( \sigma(S) \) be the sum of the terms in \( S \). Let \( H \) be a graph. The problem is to determine the smallest even \( l \) such that any \( n \)-term graphical sequence \( S \) having \( \sigma(S) \geq l \) has a realization containing \( H \) as a subgraph. Denote this value \( l \) by \( \sigma(H, n) \). We show \(\sigma(C_{2m+1}, n) = m(2n – m – 1) + 2, \quad \text{for } m \geq 3, n \geq 3m;\) \(\sigma(C_{2m+2}, n) = m(2n – m – 1) + 4, \quad \text{for } m \geq 3, n \geq 5m – 2. \)

We first prove that if \( G \) is a connected graph with \( n \) vertices and chromatic number \( \chi(G) = k \geq 2 \), then its independent domination number

\[i(G) \leq \left\lceil \frac{(k-1)}{k}n \right\rceil – (k-2).\]

This bound is tight and remains so for planar graphs. We then prove that the independent domination number of a diameter two planar graph on \( n \) vertices is at most \( \left\lceil \frac{n}{3} \right\rceil \).