Let $\mathrm{Lct}\left(G\right)$ denote the set of all lengths of closed trails that exist in an even graph $G$. A sequence $(t_1,\cdots ,t_p)$ of elements of $\mathrm{Lct}\left(G\right)$ adding up to $\left|E\right(G\left)\right|$ is $G$-realisable provided there is a sequence $(T_1,\cdots ,T_p)$ of pairwise edge-disjoint closed trails in $G$ such that $T_i$ is of length $t_i$ for $i=1,\cdots ,p$. The graph $G$ is arbitrarily decomposable into closed trails if all possible sequences are $G$-realisable. In the paper it is proved that if $a\ge 1$ is an odd integer and $M_{a,a}$ is a perfect matching in $K_{a,a}$, then the graph $K_{a,a}-M_{a,a}$ is arbitrarily decomposable into closed...

Let $P_k$ and $S_k$ denote a path and a star, respectively, on $k$ vertices. We give necessary and sufficient conditions for the existence of a complete $\{P_5,S_5\}$-decomposition of Cartesian product of complete graphs.

Häggkvist [6] proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K6n,6n. In [1] Cichacz and Froncek established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into generalized prisms of order 2n. In [2] and [3] Cichacz, Froncek, and Kovar showed decompositions of K3n/2,3n/2 into generalized prisms of order 2n. In this paper we prove that K6n/5,6n/5...

It has been shown [3] that any bipartite graph $K_{a,b}$, where a, b are even integers, can be decomposed into closed trails with prescribed even lengths. In this article, we consider the corresponding question for directed bipartite graphs. We show that a complete directed bipartite graph ${}^{\leftrightarrow }{K}_{a,b}$ is decomposable into directed closed trails of even lengths greater than 2, whenever these lengths sum up to the size of the digraph. We use this result to prove that complete bipartite multigraphs can be decomposed...

We prove that any complete bipartite graph $K_{a,b}$, where $a,b$ are even integers, can be decomposed into closed trails with prescribed even lengths.

R. Frucht and J. Gallian (1988) proved that bipartite prisms of order $2n$ have an $\alpha$-labeling, thus they decompose the complete graph $K_{6nx+1}$ for any positive integer $x$. We use a technique called the ${\rho }^{+}$-labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order $2n$ called generalized prisms decompose the complete graph $K_{6nx+1}$ for any positive integer $x$.

We analyze a minimum number of vertices of a complete graph that can be decomposed into one factor of diameter 2 and k factors of diameter at most 3. We find exact values for k ≤ 4 and the asymptotic value of the ratio of this number and k when k tends to infinity. We also find the asymptotic value of the ratio of the number of vertices of the smallest complete graph that can be decomposed into p factors of diameter 2 and k factors of diameter 3 and number k when p is fixed.

Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. λKn is the usual notation for the complete multigraph on n vertices and in which every edge is taken λ times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of λKn into edges disjoint of stars Sk’s and cycles Ck’s.

In this note, we consider the problem of existence of an edge-decomposition of a multigraph into isomorphic copies of 2-edge paths $K_{1,2}$. We find necessary and sufficient conditions for such a decomposition of a multigraph H to exist when (i) either H does not have incident multiple edges or (ii) multiplicities of the edges in H are not greater than two. In particular, we answer a problem stated by Z. Skupień.

It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each n ≥ 3. The...

For n ≥ 4, the complete n-vertex multidigraph with arc multiplicity λ is proved to have a decomposition into directed paths of arbitrarily prescribed lengths ≤ n - 1 and different from n - 2, unless n = 5, λ = 1, and all lengths are to be n - 1 = 4. For λ = 1, a more general decomposition exists; namely, up to five paths of length n - 2 can also be prescribed.

Given a family ℱ of multigraphs without isolated vertices, a multigraph M is called ℱ-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of ℱ. We present necessary and sufficient conditions for existence of such decompositions if ℱ consists of all multigraphs of size q except for one. Namely, for a multigraph H of size q we find each multigraph M of size kq, such that every partition of the edge set of M into parts of cardinality q contains a part...

Given a family 𝓕 of multigraphs without isolated vertices, a multigraph M is called 𝓕-decomposable if M is an edge disjoint union of multigraphs each of which is isomorphic to a member of 𝓕. We present necessary and sufficient conditions for the existence of such decompositions if 𝓕 comprises two multigraphs from the set consisting of a 2-cycle, a 2-matching and a path with two edges.

An arc decomposition of the complete digraph Kₙ into t isomorphic subdigraphs is generalized to the case where the numerical divisibility condition is not satisfied. Two sets of nearly tth parts are constructively proved to be nonempty. These are the floor tth class ( Kₙ-R)/t and the ceiling tth class ( Kₙ+S)/t, where R and S comprise (possibly copies of) arcs whose number is the smallest possible. The existence of cyclically 1-generated decompositions of Kₙ into cycles ${}^{\to }{C}_{n-1}$ and into paths ${}^{\to }Pₙ$ is characterized....