Consider the multigraph obtained by adding a double edge to \( K_4 – e \). Now, let \( D \) be a directed graph obtained by orientating the edges of that multigraph. We establish necessary and sufficient conditions on \( n \) for the existence of a \( (K^*_n, D) \)-design for four such orientations.

Working on general hypergraphs requires to properly redefine the concept of adjacency in a way that it captures the information of the hyperedges independently of their size. Coming to represent this information in a tensor imposes to go through a uniformisation process of the hypergraph. Hypergraphs limit the way of achieving it as redundancy is not permitted. Hence, our introduction of hb-graphs, families of multisets on a common universe corresponding to the vertex set, that we present in details in this article, allowing us to have a construction of adequate adjacency tensor that is interpretable in term of \(m\)-uniformisation of a general hb-graph. As hypergraphs appear as particular hb-graphs, we deduce two new (\(e\))-adjacency tensors for general hypergraphs. We conclude this article by giving some first results on hypergraph spectral analysis of these tensors and a comparison with the existing tensors for general hypergraphs, before making a final choice.

The paper proposes techniques which provide closed-form solutions for special simultaneous systems of two and three linear recurrences. These systems are characterized by particular restrictions on their coefficients. We discuss the application of these systems to some algorithmic problems associated with the relationship between algebraic expressions and graphs. Using decomposition methods described in the paper, we generate the simultaneous recurrences for graph expression lengths and solve them with the proposed approach.

For a given graph \(G\), a variation of its line graph is the 3-xline graph, where two 3-paths \(P\) and \(Q\) are adjacent in \(G\) if \(V(P) \cap V(Q) = \{v\}\) when \(v\) is the interior vertex of both \(P\) and \(Q\). The vertices of the 3-xline graph \(XL_3(G)\) correspond to the 3-paths in \(G\), and two distinct vertices of the 3-xline graph are adjacent if and only if they are adjacent 3-paths in \(G\). In this paper, we study 3-xline graphs for several classes of graphs, and show that for a connected graph \(G\), the 3-xline graph is never isomorphic to \(G\) and is connected only when \(G\) is the star \(K_{1,n}\) for \(n = 2\) or \(n \geq 5\). We also investigate cycles in 3-xline graphs and characterize those graphs \(G\) where \(XL_3(G)\) is Eulerian.

An \(L(h,k)\) labeling of a graph \(G\) is an integer labeling of the vertices where the labels of adjacent vertices differ by at least \(h\), and the labels of vertices that are at distance two from each other differ by at least \(k\). The span of an \(L(h,k)\) labeling \(f\) on a graph \(G\) is the largest label minus the smallest label under \(f\). The \(L(h,k)\) span of a graph \(G\), denoted \(\lambda_{h,k}(G)\), is the minimum span of all \(L(h,k)\) labelings of \(G\).

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.