A red-blue coloring of a graph \( G \) is an edge coloring of \( G \) in which every edge of \( G \) is colored red or blue. Let \( F \) be a connected graph of size 2 or more with a red-blue coloring, at least one edge of each color, where some blue edge of \( F \) is designated as the root of \( F \). Such an edge-colored graph \( F \) is called a color frame. An \( F \)-coloring of a graph \( G \) is a red-blue coloring of \( G \) in which every blue edge of \( G \) is the root edge of a copy of \( F \) in \( G \). The \( F \)-chromatic index \( \chi_F'(G) \) of \( G \) is the minimum number of red edges in an \( F \)-coloring of \( G \). A minimal \( F \)-coloring of \( G \) is an \( F \)-coloring with the property that if any red edge of \( G \) is re-colored blue, then the resulting red-blue coloring of \( G \) is not an \( F \)-coloring of \( G \). The maximum number of red edges in a minimal \( F \)-coloring of \( G \) is the upper \( F \)-chromatic index \( \chi_F”(G) \) of \( G \). For integers \( k \) and \( m \) with \( 1 \leq k < m \) and \( m \geq 3 \), let \( S_{k,m} \) be the color frame of the star \( K_{1,m} \) of size \( m \) such that \( S_{k,m} \) has exactly \( k \) red edges and \( m-k \) blue edges. For a positive integer \( k \), a set \( X \) of edges of a graph \( G \) is a \( \Delta_k \)-set if \( \Delta(G[X]) = k \), where \( G[X] \) is the subgraph of \( G \) induced by \( X \). The maximum size of a \( \Delta_k \)-set in \( G \) is referred to as the \( k \)-matching number of \( G \) and is denoted by \( a_k'(G) \). A \( \Delta_k \)-set \( X \) is maximal if \( X \cup \{e\} \) is not a \( \Delta_k \)-set for every \( e \in E(G) – X \). The minimum size of a maximal \( \Delta_k \)-set of \( G \) is the lower \( k \)-matching number of \( G \) and is denoted by \( a_k''(G) \). In this paper, we consider \( S_{k,m} \)-colorings of a graph and study relations between \( S_{k,m} \)-colorings and \( \Delta_k \)-sets in graphs. Bounds are established for the \( S_{k,m} \)-chromatic indexes \( \chi_{S_{k,m}}'(G) \) and \( \chi_{S_{k,m}}''(G) \) of a graph \( G \) in terms of the \( k \)-matching numbers \( a_k'(G) \) and \( a_k''(G) \) of the graph. Other results and questions are also presented.

Let \( G \) be a Hamiltonian graph of order \( n \geq 3 \). For an integer \(\ell\) with \(1 \leq \ell \leq n\), the graph \( G \) is \(\ell\)-path-Hamiltonian if every path of order \(\ell\) lies on a Hamiltonian cycle in \( G \). The Hamiltonian cycle extension number of \( G \) is the maximum positive integer \(\ell\) for which every path of order \(\ell\) or less lies on a Hamiltonian cycle of \( G \). For an integer \(\ell\) with \(2 \leq \ell \leq n-1\), the graph \( G \) is \(\ell\)-path-pancyclic if every path of order \(\ell\) in \( G \) lies on a cycle of every length from \(\ell+1\) to \(n\). (Thus, a \(2\)-path-pancyclic graph is edge-pancyclic.) A graph \( G \) of order \( n \geq 3 \) is path-pancyclic if \( G \) is \(\ell\)-path-pancyclic for each integer \(\ell\) with \(2 \leq \ell \leq n-1\). In this paper, we present a brief survey of known results on these two parameters and investigate the \(\ell\)-path-Hamiltonian graphs and \(\ell\)-path-pancyclic graphs having small minimum degree and small values of \(\ell\). Furthermore, highly path-pancyclic graphs are characterized and several well-known classes of \(2\)-path-pancyclic graphs are determined. The relationship among these two parameters and other well-known Hamiltonian parameters is investigated along with some open questions in this area of research.

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \). A \((p, q)\)-graph \( G = (V, E) \) is said to be AL(\(k\))-traversal if there exists a sequence of vertices \((v_1, v_2, \ldots, v_p)\) such that for each \( i = 1, 2, \ldots, p-1 \), the distance between \( v_i \) and \( v_{i+1} \) is equal to \( k \). We call a graph \( G \) a 2-steps Hamiltonian graph if it has an AL(2)-traversal in \( G \) and \( d(v_p, v_1) = 2 \). In this paper, we characterize some cubic graphs that are 2-steps Hamiltonian. We show that no forbidden subgraph characterization for non-2-steps-Hamiltonian cubic graphs is available by demonstrating that every cubic graph is a homeomorphic subgraph of a non-2-steps Hamiltonian cubic graph.

For a graph \(G = (V, E)\) and a coloring \(f : V(G) \to \mathbb{Z}_2\), let \(v_f(i) = |f^{-1}(i)|\). \(f\) is said to be friendly if \(|v_f(1) – v_f(0)| \leq 1\). The coloring \(f : V(G) \to \mathbb{Z}_2\) induces an edge labeling \(f_+ : E(G) \to \mathbb{Z}_2\) defined by \(f_+(xy) = |f(x) – f(y)|\), for all \(xy \in E(G)\). Let \(e_f(i) = |f_+^{-1}(i)|\). The friendly index set of the graph \(G\), denoted by \(FI(G)\), is defined by
\[
FI(G) = \{ |e_f(1) – e_f(0)| : f \text{ is a friendly vertex labeling of } G \}.
\]

In this paper, we determine the friendly index set of certain classes of trees and introduce a few classes of fully cordial trees.

Let \( G = (V(G), E(G)) \) be a simple, finite, and undirected graph with \( n \) vertices. Given a bijection \( f : V(G) \to \{1, \dots, n\} \), one can associate two integers \( S = f(u) + f(v) \) and \( D = |f(u) – f(v)| \) with every edge \( uv \in E(G) \). The labeling \( f \) induces an edge labeling \( f’ : E(G) \to \{0, 1\} \) such that for any edge \( uv \) in \( E(G) \), \( f'(uv) = 1 \) if \(\gcd(S, D) = 1\), and \( f'(uv) = 0 \) otherwise. Such a labeling is called an SD-prime labeling if \( f'(uv) = 1 \) for all \( uv \in E(G) \). We say that \( G \) is SD-prime if it admits an SD-prime labeling. A graph \( G \) is said to be a \({strongly \;SD-prime \;graph}\) if for every vertex \( v \) of \( G \) there exists an SD-prime labeling \( f \) satisfying \( f(v) = 1 \). In this paper, we first give some sufficient conditions for a theta graph to be strongly SD-prime. We then provide constructions of new SD-prime graphs from known SD-prime graphs and investigate the SD-primality of some general graphs.

Recently, the authors proposed a fundamental theorem for the decomposing of a complete bipartite graph. They applied the theorem to obtain complete results on the decomposition of a complete bipartite graph into connected subgraphs on four vertices and up to four edges. In this paper, we decompose a complete multi-bipartite graph into its subgraphs of four vertices and five edges. We show that necessary conditions are sufficient for the decompositions, with some exceptions where decompositions do not exist

The authors previously defined the Stanton-type graph \(S(n,m)\) and demonstrated how to decompose \(\lambda K_n\) (for the appropriate minimal values of \(\lambda\)) into Stanton-type graphs \(S(4, 3)\) of the LOE-, OLE-, LEO-, and ELO-types. Sarvate and Zhang showed that for all possible values of \(\lambda\), the necessary conditions are sufficient for LOE- and OLE-decompositions. In this paper, we show that for all possible values of \(\lambda\), the necessary conditions are sufficient for LEO- and ELO-decompositions.

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A \((p, q)\)-graph \(G = (V, E)\) is said to be \(AL(k)\)-traversal if there exists a sequence of vertices \(\{v_1, v_2, \ldots, v_p\}\) such that for each \(i = 1, 2, \ldots, p-1\), the distance between \(v_i\) and \(v_{i+1}\) is equal to \(k\). We call a graph \(G\) a \(k\)-steps Hamiltonian graph if it has an \(AL(k)\)-traversal in \(G\) and the distance between \(v_p\) and \(v_1\) is \(k\). In this paper, we completely classify whether a subdivision graph of a cycle with a chord is \(2\)-steps Hamiltonian.

A triple system is decomposable if the blocks can be partitioned into two sets, each of which is itself a triple system. It is cyclically decomposable if the resulting triple systems are themselves cyclic. In this paper, we prove that a cyclic two-fold triple system is cyclically indecomposable if and only if it is indecomposable. Moreover, we construct cyclic three-fold triple systems of order $v$ which are cyclically indecomposable but decomposable for all \(v \equiv 3 \mod 6\). The only known example of a cyclic three-fold triple system of order \(v \equiv 1 \mod 6\) that is cyclically indecomposable but decomposable was a triple system on 19 points. We present a construction which yields infinitely many such triple systems of order \(v \equiv 1 \mod 6\). We also give several examples of cyclically indecomposable but decomposable cyclic four-fold triple systems and few constructions that yield infinitely many such triple systems.

The spectrum problem for decomposition of trees with up to eight edges was introduced and solved in 1978 by Huang and Rosa. Additionally, the packing problem was settled for all trees with up to six edges by Roditty. For the first time, we consider obtaining all possible leaves in a maximum tree-packing of \(K_n\), which we refer to as the spectrum problem for packings of complete graphs. In particular, we completely solve this problem for trees with at most five edges. The packing designs are used in developing optimal error-correcting codes, which have applications in biology, such as in DNA sequencing.