Let \( G \) be a finite \( 4 \)-regular cyclically \( 2k \)-edge-connected simple graph for some integer \( k \geq 1 \). Let \( E(k) \) be a set of \( k \) independent edges in \( G \) and \( (E_1, E_2) \) be a partition of \( E(k) \). We consider when there exists a \( 2 \)-factor in \( G \) which excludes all edges of \( E_1 \), and includes all the edges of \( E_2 \). A complete characterization is provided.

If an edge-disjoint decomposition of a complete graph of order \( n \) into copies of a \( 3 \)-star (i.e., the graph \( K_{1,3} \) on \( 4 \) vertices) is taken, and if these \( 3 \)-stars can be paired up in three distinct ways to form a graph on \( 6 \) vertices consisting of a \( 4 \)-cycle with two opposite pendant edges, such that:
(1) in each of the three pairings, there exists a metamorphosis into a \( 4 \)-cycle system; (2) taking precisely those \( 4 \)-cycles formed from the two pendant edges from each pair of \( 3 \)-stars, in each of the three metamorphoses, we again have a \( 4 \)-cycle system of the complete graph, then this is called a complete set of metamorphoses from paired \( 3 \)-stars into \( 4 \)-cycles.

We show that such a complete set of metamorphoses from paired \( 3 \)-stars into \( 4 \)-cycles exists if and only if the order of the complete graph is \( 1 \) or \( 9 \pmod{24} \), and greater than \( 9 \).

Let \( G \) be a connected graph of order \( n \geq 3 \) and size \( m \), and let \( f: E(G) \to \mathbb{Z}_n \) be an edge labeling of \( G \). Define an induced vertex labeling \( f’: V(G) \to \mathbb{Z}_n \) in terms of \( f \) by \( f'(v) = \sum_{u \in N(v)} f(uv) \), where the sum is computed in \( \mathbb{Z}_n \). If \( f’ \) is one-to-one, then \( f \) is called a modular edge-graceful labeling and \( G \) is a modular edge-graceful graph. It is known that no connected graph of order \( n \geq 3 \) with \( n \equiv 2 \pmod{4} \) is modular edge-graceful. A 1991 conjecture states that every tree of order \( n \) where \( n \not\equiv 2 \pmod{4} \) is modular edge-graceful. In this work, we show that this conjecture is true and furthermore that a nontrivial connected graph of order \( n \) is modular edge-graceful if and only if \( n \not\equiv 2 \pmod{4} \). The modular edge-gracefulness \(\text{meg}(G)\) of a connected graph \( G \) of order \( n \geq 3 \) is the smallest integer \( k \geq n \) for which there exists an edge labeling \( f: E(G) \to \mathbb{Z}_k \) such that the induced vertex labeling \( f’: V(G) \to \mathbb{Z}_k \) is one-to-one. It is shown that \(\text{meg}(G) = n+1\) for every connected graph \( G \) that is not modular edge-graceful.

A dominating set is a vertex subset \(D\) of a graph \(G\) such that each vertex of \(G\) is either in \(D\) or adjacent to a vertex in \(D\). The domination number, \(\gamma(G)\), is the minimum cardinality of a dominating set of a graph \(G\). In this paper, we will investigate the domination number of Fibonacci cubes. We firstly study the degree sequence of the Fibonacci cubes. Then, a lower bound for the domination number of Fibonacci cube of order \(n\) is obtained, and the exact value of the domination number of Fibonacci cubes of order at most \(8\) is determined.

Let \( L(m, n) \) be the largest integer such that, if each symbol in an \( m \times n \) rectangle occurs at most \( L(m, n) \) times, then the array must have a transversal. We improve the lower bound to \( L(m, n) \geq \left\lfloor \frac{m(n – m + 1) – 1}{m – 1} \right\rfloor \) for \( m > 1 \). Then we show that sporadically \( L(m, n) < \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \) in the range \( m \leq n \leq m^2 – 3m + 3 \). Define \( n_0(m) \) to be the smallest integer \( z \) such that if \( n \geq z \) then \( L(m, n) = \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \). We improve \( n_0(m) \) from \( O(m^3) \) to \( O(m^{2.5}) \). Finally, we determine \( L(4, n) \) for all \( n \).

In [1], we showed that for \( v \equiv 1 \) or \( 3 \pmod{6} \), there is an equitable \( k \)-edge coloring of \( K_v \) that does not admit any polychromatic \( STS(v) \), when \( k = 2, 3 \), and \( v – 2 \). In this paper, we extend the results to all feasible values of \( k \), where \( 2 \leq k \leq v – 2 \).

A Costas Latin square of order \( n \) is a set of \( n \) disjoint Costas arrays of the same order. Costas Latin squares are studied here from both a construction and classification point of view. A complete classification is carried out up to order \( 27 \). In this range, we verify the conjecture that there is no Costas Latin square for any odd order \( n \geq 3 \). Various other related combinatorial structures are also considered, including near Costas Latin squares (which are certain packings of near Costas arrays) and Vatican Costas squares.

Let \(G = (V,E)\) be an undirected graph and let \(\pi = \{V_1, V_2, \ldots, V_k\}\) be a partition of the vertices \(V\) of \(G\) into \(k\) blocks \(V_i\). From this partition one can construct the following digraph \(D(\pi) = (\pi, E(\pi))\), the vertices of which correspond one-to-one with the \(k\) blocks \(V_i\) of \(\pi\), and there is an arc from \(V_i\) to \(V_j\) if every vertex in \(V_j\) is adjacent to at least one vertex in \(V_i\), that is, \(V_i\) dominates \(V_j\). We call the digraph \(D(\pi)\) the domination digraph of \(\pi\). A triad is one of the 16 digraphs on three vertices having no loops or multiple arcs. In this paper we study the algorithmic complexity of deciding if an arbitrary graph \(G\) has a given digraph as one of its domination digraphs, and in particular, deciding if a given triad is one of its domination digraphs. This generalizes results for the domatic number.

A Roman dominating function on a graph \( G \) is a function \( f: V(G) \to \{0,1,2\} \) such that every vertex \( u \) with \( f(u) = 0 \) is adjacent to a vertex \( v \) with \( f(v) = 2 \). The weight of a Roman dominating function \( f \) is the value \( f(V(G)) = \sum_{u \in V(G)} f(u) \). A Roman dominating function \( f \) is an independent Roman dominating function if the set of vertices for which \( f \) assigns positive values is independent. The independent Roman domination number \( i_R(G) \) of \( G \) is the minimum weight of an independent Roman dominating function of \( G \).

We show that if \( T \) is a tree of order \( n \), then \( i_R(T) \leq \frac{4n}{5} \), and characterize the class of trees for which equality holds. We present bounds for \( i_R(G) \) in terms of the order, maximum and minimum degree, diameter, and girth of \( G \). We also present Nordhaus-Gaddum inequalities for independent Roman domination numbers.

Let \( M(b, n) \) be the complete multipartite graph with \( b \) parts \( B_0, \ldots, B_{b-1} \) of size \( n \). A \( 4 \)-cycle system of \( M(b, n) \) is said to be a \emph{frame} if the \( 4 \)-cycles can be partitioned into sets \( S_1, \ldots, S_z \) such that for \( 1 \leq j \leq z \), \( S_j \) induces a \( 2 \)-factor of \( M(b, n) \setminus B_i \) for some \( i \in \mathbb{Z}_b \). The existence of a \( C_4 \)-frame of \( M(b, n) \) has been settled when \( n = 4 \) [6]. In this paper, we completely settle the existence question of a \( C_4 \)-frame of \( M(b, n) \) for all \( b \neq 2 \) and \( n \).