In this paper, we use standard graph labeling techniques to prove that each tri-cyclic graph with eight edges decomposes the complete graph \(K_n\) if and only if \(n \equiv 0, 1 \pmod{16}\). We apply \(\rho\)-tripartite labelings and 1-rotational \(\rho\)-tripartite labelings.

We introduce a variation of \(\sigma\)-labeling to prove that every disconnected unicyclic bipartite graph with eight edges decomposes the complete graph \(K_n\) whenever the necessary conditions are satisfied. We combine this result with known results in the connected case to prove that every unicyclic bipartite graph with eight edges other than \(C_8\) decomposes \(K_n\) if and only if \(n \equiv 0, 1 \pmod{16}\) and \(n > 16\).

Let \( G \) be a tripartite unicyclic graph with eight edges that either (i) contains a triangle or heptagon, or (ii) contains a pentagon and is disconnected. We prove that \( G \) decomposes the complete graph \( K_n \) whenever the necessary conditions are satisfied. We combine this result with other known results to prove that every unicyclic graph with eight edges other than \( C_8 \) decomposes \( K_n \) if and only if \( n \equiv 0,1 \pmod{16} \).

For a positive integer \( k \), let \( P^*([k]) \) denote the set of nonempty subsets of \( [k] = \{1, 2, \ldots, k\} \). For a graph \( G \) without isolated vertices, let \( c: E(G) \rightarrow P^*([k]) \) be an edge coloring of \( G \) where adjacent edges may be colored the same. The induced vertex coloring \( c’ : V(G) \rightarrow P^*([k]) \) is defined by \( c'(v) = \bigcap_{e \in E_v} c(e) \), where \( E_v \) is the set of edges incident with \( v \). If \( c’ \) is a proper vertex coloring of \( G \), then \( c \) is called a regal \( k \)-edge coloring of \( G \). The minimum positive integer \( k \) for which a graph \( G \) has a regal \( k \)-edge coloring is the regal index of \( G \). If \( c’ \) is vertex-distinguishing, then \( c \) is a strong regal \( k \)-edge coloring of \( G \). The minimum positive integer \( k \) for which a graph \( G \) has a strong regal \( k \)-edge coloring is the strong regal index of \( G \). The regal index (and, consequently, the strong regal index) is determined for each complete graph and for each complete multipartite graph. Sharp bounds for regal indexes and strong regal indexes of connected graphs are established. Strong regal indexes are also determined for several classes of trees. Other results and problems are also presented.

A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree \( T \) with \( n \) edges, it is conjectured that there exists a labeling \( f: V(T) \rightarrow \{0, 1, \ldots, n\} \) such that the set of induced edge labels \( \{ |f(u) – f(v)| : \{u,v\} \in E(T) \} \) is exactly \( \{1, 2, \ldots, n\} \). We extend this concept to allow for multigraphs with edge multiplicity at most 2. A 2-fold graceful labeling of a graph (or multigraph) \( G \) with \( n \) edges is a one-to-one function \( f: V(G) \rightarrow \{0, 1, \ldots, n\} \) such that the multiset of induced edge labels is comprised of two copies of each element in \( \{1, 2, \ldots, \lfloor n/2 \rfloor\} \), and if \( n \) is odd, one copy of \( \{\lfloor n/2 \rfloor\} \). When \( n \) is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length \( n \neq 1 \mod 4 \), and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is 2-fold graceful.

We develop an ordering function on the class of tournament digraphs (complete antisymmetric digraphs) that is based on the Rényi \(\alpha\)-entropy. This ordering function partitions tournaments on \(n\) vertices into equivalence classes that are approximately sorted from transitive (the arc relation is transitive — the score sequence is \((0, 1, 2, \ldots, n-1)\)) to regular (score sequence like \((\frac{n-1}{2}, \ldots, \frac{n-1}{2})\)). However, the diversity among regular tournaments is significant; for example, there are 1,123 regular tournaments on 11 vertices and 1,495,297 regular tournaments on 13 vertices up to isomorphism, which is captured to an extent.

Given a graph \( G \), we are interested in finding disjoint paths for a given set of distinct pairs of vertices. In 2017, we formally defined a new parameter, the pansophy of \( G \), in the context of the disjoint path problem. In this paper, we develop an algorithm for computing the pansophy of graphs and illustrate the algorithm on graphs where the pansophy is already known. We close with future research directions.

Let \( G \) be one of the two multigraphs obtained from \( K_4-e \) by replacing two edges with a double-edge while maintaining a minimum degree of 2. We find necessary and sufficient conditions on \( n \) and \(\lambda\) for the existence of a \( G \)-decomposition of \( K_n \).

Let \( m \) and \( n \) be positive integers, and let \( R = (r_1, \ldots, r_m) \) and \( S = (s_1, \ldots, s_n) \) be non-negative integral vectors. Let \( \mathcal{A}(R, S) \) be the set of all \( m \times n \) \((0,1)\)-matrices with row sum vector \( R \) and column vector \( S \). Let \( R \) and \( S \) be non-increasing, and let \( F(R, S) \) be the \( m \times n \) \((0,1)\)-matrix where for each \( i \), the \( i^{\text{th}} \) row of \( F(R, S) \) consists of \( r_i \) 1’s followed by \( n – r_i \) 0’s, called Ferrers matrices. The discrepancy of an \( m \times n \) \((0,1)\)-matrix \( A \), \( \text{disc}(A) \), is the number of positions in which \( F(R, S) \) has a 1 and \( A \) has a 0. In this paper we investigate linear operators mapping \( m \times n \) matrices over the binary Boolean semiring to itself that preserve sets related to the discrepancy. In particular we characterize linear operators that preserve both the set of Ferrers matrices and the set of matrices of discrepancy one.

The line graph \( L(G) \) of a nonempty graph \( G \) has the set of edges in \( G \) as its vertex set where two vertices of \( L(G) \) are adjacent if the corresponding edges of \( G \) are adjacent. Let \( k > 2 \) be an integer and let \( G \) be a graph containing k-paths (paths of order \( k \)). The k-path graph \( P_k(G) \) of \( G \) has the set of k-paths of \( G \) as its vertex set where two distinct vertices of \( P_k(G) \) are adjacent if the corresponding k-paths of \( G \) have a \( (k-1) \)-path in common. Thus, \( P_2(G) = L(G) \) and \( P_3(G) = L(L(G)) \). Hence, the k-path graph \( P_k(G) \) of a graph \( G \) is a generalization of the line graph \( L(G) \). Let \( G \) be a connected graph of order \( n > 3 \) and let \( k \) be an integer with \( 2 < k 2 \), then \( P_3(T) \) is \( k \)-tree-connected. This conjecture was verified for \( k = 2, 3 \). In this work, we show that if \( T \) is a tree of order at least 6 containing no vertices of degree 2, 3, 4, or 5, then \( P_3(T) \) is 4-tree-connected and so verify the conjecture for the case when \( k = 4 \).