Gregarious Decompositions of Complete Equipartite Graphs and Related Structures

Abstract

In a finite mathematical structure with a given partition, a substructure is said to be gregarious if either it meets each partition class or it shares at most one element with each partition class. In this paper, we considered edge decompositions of graphs and hypergraphs into gregarious subgraphs and subhypergraphs. We mostly dealt with “complete equipartite” graphs and hypergraphs, where the vertex classes have the same size and precisely those edges or hyperedges of a fixed cardinality are present that do not contain more than one element from any class. Some related graph classes generated by product operations were also considered. The generalization to hypergraphs offers a wide open area for further research.

1. Introduction

Decomposition techniques are of very high importance, in both theory and practice, with an ever-growing number of applications. There is a huge literature on this approach in many areas. At the time of writing this note, the citation database Google Scholar [1] returns approximately 4,140,000 answers to the search of “decomposition”, and the repository arXiv [2] offers 8566 manuscripts with this word in the title and 36,070 in the contents of their archived scientific works, respectively, about 80.5% and 71% of them belonging to the disciplines of mathematics and computer science.

In this paper, we present a study of discrete mathematical structures that enjoy a very high degree of symmetry. Important classes of this kind are the complete equipartite graphs and their generalization to uniform hypergraphs (set systems). We also dealt with more-general structures, obtained via product operations, that inherit symmetry properties from their components. Decompositions of these combinatorial objects into isomorphic edge-disjoint sub(hyper)graphs were considered. In graphs, we concentrated on the case of cycles, and in hypergraphs, we solved the first problem that arises in the area of gregarious decompositions.

A very interesting account of the history of block designs was given in Chapter I.2 of [3], starting on page 12. The earliest publications mentioned there date back to the 1830s and 1840s. Some of those results can equivalently be formulated as edge decompositions of complete graphs into cycles of length three. Another root of graph decomposition theory is the edge decomposition of complete graphs on n vertices into cycles of length n, as accounted in [4]. Since then, a huge number of works have dealt with graph and hypergraph decompositions.

In the particular type of “gregarious” decompositions of a graph, it is assumed that a partition of the vertex set is given, and the subgraphs taken for the decomposition must intersect the partition classes in a prescribed way. We give the precise definitions in Section 3. In Section 4, we present a detailed survey on the literature of this area.

Researchwise, our goal here was twofold. In one direction, we provide contributions concerning a problem raised a decade ago by Cho, Park, and Sano ([5] p. 62), who asked for “gregarious long cycle decompositions having some additional conditions such as resolvable decompositions and circulant decompositions”. The corresponding new results of Section 5 give sufficient arithmetic conditions for the decomposability of graphs obtained by a combination of two types of graph products and, also, for the resolvable decomposability of complete equipartite graphs. For the constructed decompositions of complete multipartite graphs, a well-described type of symmetry is guaranteed, as well. In another direction, we introduce the analogous problem for hypergraphs, hence opening a new area for research in the future. We prove the first result of this kind in Section 6, solving the most-natural basic case.

The structure of the paper is as follows. The general notation and some graph product operations are described in Section 2, and notions concerning the edge decompositions of graphs are introduced in Section 3. In Section 4, the literature on gregarious decompositions is surveyed. New results on the existence of resolvable gregarious decompositions of graphs into cycles are proven in Section 5. Uniform hypergraphs are considered in Section 6, and some concluding remarks are given in Section 7.

2. Some Basic Graphs and Product Operations

Standard graph-theoretic notation will be used; for terms not introduced here, we refer to [6].

As usual, the vertex set and the edge set of a graph G will be denoted by $V(G)$ and $E(G)$, respectively. For any positive integer n, we write $K_n$, $P_n$, and $C_n$ for the complete graph, the path, and the cycle on n vertices (assuming $n\ge 3$ in case of cycles); the term “n-cycle” is standard for $C_n$ and will also be used in the sequel. Further, we write $S_n$ for the symmetric group formed by all the $n!$ permutations of a set of n elements.

Definition 1.

Let $m,n$ be positive integers, $n\ge 2$. The complete equipartite graph—also termed “balanced complete multipartite graph”—is the graph that has n mutually disjoint vertex classes $V_1,V_2,\dots ,V_n$, with $|V_1| =\dots = |V_n| =m$, where any two vertices in the same class are nonadjacent and any two vertices belonging to distinct classes are adjacent. This graph will be denoted by $K_{n\ast m}$. (In several papers the notation $K_{n(m)}$ is used for the same.)

Obviously, $K_{n\ast m}$ has $mn$ vertices and $e_{n\ast m}:=\left(\genfrac{}{}{0pt}{}{n}{2}\right)m^2=\frac{m^{2}n(n-1)}{2}$ edges. The case of $m=1$ just means the complete graph $K_n$; it is the most symmetric connected graph; its automorphism group is the symmetric group, $\mathrm{Aut}(K_n)=S_n$. More generally, in complete equipartite graphs, one can take any permutation of the vertex classes and, also, any permutation of the vertices inside each class; hence, $\mathrm{Aut}(K_{n\ast m})=S_n\times {(S_m)}^n$.

The graphs $K_{n\ast m}$ may be viewed in the way that they are obtained from $K_n$ by substituting an independent set of size m into each vertex. This operation is often referred to as “blowing up points” or the “expanding points method”. In fact, these graphs belong to a class generated by a type of graph product.

Definition 2.

The lexicographic product—or wreath product, or composition—of two graphs G and H, denoted by $G\circ H$, is the graph whose vertex set is the Cartesian product:

$$V(G\circ H)=V(G)\times V(H)=\{(g,h)\mid g\in V(G),h\in V(H)\}$$

and whose edge set is

$$E(G\circ H)=\{(g,h)(g^{\prime },h^{\prime })\mid \mathrm{either}g{g}^{\prime }\in E(G),\mathrm{or}g=g^{\prime }\mathrm{and}h{h}^{\prime }\in E(H)\}.$$

A small illustrative example is the lexicographic product of $P_2$ and $P_3$; it also demonstrates that ∘ is not commutative. The graph $P_2\circ P_3$ has two vertex classes, say $V_1$ and $V_2$, each with three vertices, and each $V_i$ induces a $P_3$. Hence two edges are missing from the complete graph of order six, $P_2\circ P_3\cong K_6-2K_2$. On the other hand, $P_3\circ P_2$ has three vertex classes, say $V_1^{\prime },V_2^{\prime },V_3^{\prime }$, each of them containing two adjacent vertices; moreover, $V_2^{\prime }$ is completely adjacent to $V_1^{\prime }\cup V_3^{\prime }$, while there is no edge between $V_1^{\prime }$ and $V_3^{\prime }$. Hence, a 4-cycle is missing from the complete graph of order six, $P_3\circ P_2\cong K_6-C_4$.

It follows from the definitions that ${\mathrm{Aut}(G\circ H)\supseteq \mathrm{Aut}(G)\times \mathrm{Aut}(H))}^{|V(G)|}$; but, here, equality does not hold in general. A simple counterexample is seen by the equality $K_{nm}=K_n\circ K_m$. On the other hand, we have equality for $K_{n\ast m}=K_n\circ {\overline{K}}_m$, where the complementary graph ${\overline{K}}_m$ is the edgeless graph with m vertices. Analogous to $K_{n\ast m}$, we shall use the notation $C_{n\ast m}$ for the “blown-up cycle” $C_n\circ {\overline{K}}_m$, assuming $n\ge 3$. It has $n{m}^2$ edges, and $\mathrm{Aut}(C_{n\ast m})={\mathbb{Z}}_2\times {\mathbb{Z}}_n\times {(S_m)}^n$. The general theory of symmetries in lexicographic products of graphs is discussed in Chapter 10.5 of [6].

There exist several further types of graph products. Here, we mention the following one, which has been studied to some extent in the context of gregarious decompositions as well.

Definition 3.

The direct product—or categorical product, or tensor product—of two graphs G and H, denoted by $G\times H$, is the graph that has vertex set $V(G)\times V(H)$, and whose edge set is

$$E(G\times H)=\{(g,h)(g^{\prime },h^{\prime })\mid g{g}^{\prime }\in E(G)\mathrm{and}h{h}^{\prime }\in E(H)\}.$$

(For this type of graph product, several further names occur in the literature; cf., e.g., page 36 of [6].)

For example, labeling the vertices of $K_2\times K_3$ as $v_{1,1},v_{1,2},v_{1,3},v_{2,1},v_{2,2},v_{2,3}$, the product graph has the following edges: $v_{1,1}{v}_{2,2}$, $v_{1,1}{v}_{2,3}$, $v_{1,2}{v}_{2,1}$, $v_{1,2}{v}_{2,3}$, $v_{1,3}{v}_{2,1}$, $v_{1,3}{v}_{2,2}$. Hence, $K_2\times K_3\cong C_6$. One may also check that $P_2\times P_3\cong 2P_3$.

A particular elementary property of the × operation is that if both G and H are bipartite, then $G\times H$ is disconnected. This fact is not hard to see: consider the bipartitions $V(G)=V_{1,G}\cup V_{2,G}$ and $V(H)=V_{1,H}\cup V_{2,H}$ of G and H into independent sets, and observe that there is no edge connecting $(V_{1,G}\times V_{1,H})\cup (V_{2,G}\times V_{2,H})$ to $(V_{1,G}\times V_{2,H})\cup (V_{2,G}\times V_{1,H})$ because the subgraph induced by each of the four sets $V_{1,G}$, $V_{2,G}$, $V_{1,H}$, $V_{2,H}$ is edgeless.

The general theory of symmetries in the lexicographic products of graphs is discussed in Chapter 8.6 of [6].

The notation $G\times H$ visually expresses the fact that $K_2\times K_2\cong 2K_2$ (two disjoint edges), while the notation $G\circ H$ follows the tradition concerning the composition of functions.

As a general approach to the current subject, assuming $V(G)=\{g_1,\dots ,g_n\}$, for both $V(G)\times V(H)$ and $V(G)\circ V(H)$, the default is to consider the vertex partition $(V_1,\dots ,V_n)$, where

$$V_i=\{(g_i,h)\mid h\in V(H)\}$$

for $i=1,\dots ,n$. This convention is compatible with the vertex partition of $K_{n\ast m}$. It applies for products with more terms, as well. For example, in $G\times (H_1\circ H_2)$ or $G\circ (H_1\circ H_2)$, the vertex partition is always taken with respect to the first term, namely G.

3. Decompositions, Gregarious Subgraphs, and Resolvable Systems

Let us begin this section with recalling the following standard definitions.

Definition 4.

Let G be any graph:

$(i)$

A decomposition (or edge decomposition) of G is a collection $\mathcal{F}=\{F_1,\dots ,F_s\}$ of mutually edge-disjoint subgraphs whose union is G. Formally, $E(F_i)\cap E(F_j)=⌀$ for all $1\le i<j\le s$, and ${\bigcup }_{i=1}^{s}E(F_i)=E(G)$.

$(ii)$

For a specified graph F, a decomposition $\mathcal{F}=\{F_1,\dots ,F_s\}$ of G is called an F-decomposition if all $F_i$ are isomorphic to F.

$(iii)$

A decomposition $\mathcal{F}=\{F_1,\dots ,F_s\}$ of G is called resolvable if it admits a partition into subsystems ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_r$—termed resolution classes or parallel classes—such that each class ${\mathcal{F}}_i$ satisfies the condition ${\bigcup }_{F_j\in {\mathcal{F}}_i}V(F_j)=V(G)$, and ${\mathcal{F}}_1\cup \cdots \cup {\mathcal{F}}_r=\mathcal{F}$ holds with ${\mathcal{F}}_i\cap {\mathcal{F}}_j=⌀$ for all $1\le i<j\le r$.

Gregarious subgraphs have been introduced gradually in the literature in different formal ways, depending on the size of subgraphs under consideration, as follows.

Definition 5.

Let a graph G with a partition $(V_1,\dots ,V_n)$ of $V(G)$ with n vertex classes be given; let $F\subset G$ be any subgraph:

(G1) 

If $|V(F)|<n$, then F is called a gregarious subgraph of G if no two vertices of F are in the same class.

(G2) 

If $|V(F)|=n$, then F is called a gregarious subgraph of G if each class contains exactly one vertex of F.

(G3) 

If $|V(F)|>n$, then F is called a gregarious subgraph of G if F meets every class.

As one may observe, all three conditions can be formulated in the following unified way:

$(\star )$

A subgraph F of G is gregarious (with respect to a specified vertex partition of G into n classes) if F has vertices in precisely

$$min(n,|V(F)|)$$

classes of G; i.e., if F intersects as many classes of G as possibly allowed by the parameters.

The combination of Definitions 4 and 5 leads to the following notion.

Definition 6.

An F-decomposition $F_1,\dots ,F_s$ of a graph G with its given vertex partition $(V_1,\dots ,V_n)$ is called a gregarious F-system—or gregarious F-decomposition—of G if each $F_i$ is a gregarious subgraph of G. Resolvable gregarious F-systems/-decompositions are defined analogously, adopting the additional requirement described in Definition 4 $(iii)$.

It follows from the definitions that, in general, the number of subgraphs $F_i$ in an F-decomposition of G is $|E(G)|/|E(F)|$, and if $\mathcal{F}$ is resolvable, then each parallel class consists of $|V(G)|/|V(F)|$ subgraphs; hence, the number of parallel classes is $\frac{|E(G)|·|V(F)|}{|V(G)|·|E(F)|}$. In particular, if $G=K_{n\ast m}$, then $\mathcal{F}$ includes $\frac{e_{n\ast m}}{|E(F)|}=\frac{m^{2}n(n-1)}{2|E(F)|}$ subgraphs, and the number of parallel classes is $\frac{mn-m}{2}·\frac{|V(F)|}{|E(F)|}$ if $\mathcal{F}$ is resolvable. Similarly, if $G=C_{n\ast m}$, then $\mathcal{F}$ includes $\frac{m^{2}n}{|E(F)|}$ subgraphs and $\frac{m·|V(F)|}{|E(F)|}$ parallel classes. In most of the literature on gregarious decompositions, the specified graph F is a cycle (hence, $|V(F)|=|E(F)|$) or even the n-cycle with $|V(F)|=|E(F)|=n$, in which cases the above formulae become quite simple.

4. A Survey on Gregarious Systems

Several types of systems automatically satisfied the “gregarious” property much before the introduction of this notion. Immediate examples are the subgraphs of bipartite graphs, as each edge meets both vertex classes. Also, the case of $m=1$ in $K_{n\ast m}$ just means edge decompositions of the complete graph $K_n$. Moreover, in the field of Design Theory, the extensively studied Group Divisible Designs of index one are equivalent to edge decompositions of complete multipartite graphs into complete subgraphs of given sizes.

All three are huge areas of research, whose survey is far beyond the scope of the present work. Here, we mention just two fundamental results on cycle decompositions. Sotteau [7] proved that the complete bipartite graph $K_{m,n}$ is decomposable into cycles of length $2k$ if and only if both m and n are even integers no smaller than k and $mn$ is a multiple of $2k$. Moreover, the results of Alspach and Gavlas [8], Šajna [9], and Buratti [10] together yield that the complete graph $K_n$ is decomposable into cycles $C_k$ if and only if n is odd and $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ is a multiple of k. The Handbook [3] provides a collection of results and references concerning Block Designs and Group Divisible Designs (Parts II and IV), cycle decompositions of complete graphs/multigraphs/directed graphs (Chapter VI.12), and also, various other types of decompositions into subgraphs (Chapter VI.24).

The first work explicitly dealing with gregarious systems was performed by Billington and Hoffman [11], who studied the case $n=3$ and $F=C_4$, hence under the definition (G3). They characterized those complete three-partite graphs (also, the non-balanced ones) that admit gregarious $C_4$-decompositions. At the end of their paper, they noted, leaving the proof to the reader, that the case of $n=4$ for $F=C_4$ (hence, the condition (G2) for 4-cycles) is simple and that the gregariously decomposable complete four-partite graphs are exactly of the form $K_{4\ast m}$ with even m. Later, the same authors [12] analyzed also $n>4$ for $F=C_4$, which means the condition (G1). Besides $K_{n\ast m}$, complete multipartite graphs with one vertex class of different size were studied. Independently and simultaneously with the preprint version of [12], the 4-cycle systems over $K_{n\ast m}$ were considered with additional requirements of symmetry in the unpublished manuscript by Cho, Ferrara, Gould, and Schmitt [13] and, later, in the closely related publication by Kim, Cho, and Cho [14].

Also, the later works on gregarious systems mostly dealt with cycles. There are clear necessary conditions for the existence of any decomposition of $K_{n\ast m}$ into k-cycles, no matter whether or not the gregarious assumption $(\star )$ is imposed. Namely, given a cycle length k, let us say that a pair $(n,m)$ is admissible for $C_k$ if the following holds:

$\langle A^{\ast }\rangle$

The vertex degrees $(n-1)m$ are even, and the number $e_{n\ast m}=\frac{1}{2}{m}^{2}n(n-1)$ of edges is a multiple of k.

For convenience, in

Table 1. The condition $\langle A^{\ast }\rangle$ for cycles $C_k$ of lengths $k=4,5,6,8$.

${\mathit{C}}_4$		${\mathit{C}}_5$
m	n	m (mod 10)	n
even	any	0	any
odd	1 (mod 8)	5	odd
	$1,3,7,9$	$1,5$	(mod 10)
		$2,4,6,8$	$0,1$ (mod 5)
$C_6$		$C_8$
m (mod 6)	n	m (mod 4)	n
0	any	0	any
3	1 (mod 4)	2	$0,1$ (mod 4)
$2,4$	$0,1$ (mod 3)	$1,3$	1 (mod 16)
$1,5$	$1,9$ (mod 12)

, we collect the explicit form of $\langle A^{\ast }\rangle$ in terms of residue classes for the small values $k=4,5,6,8$; those are the cycle lengths for which, so far, it has been proven that $\langle A^{\ast }\rangle$ is not only necessary, but also sufficient for the existence of a gregarious $C_k$-system over the entire class of $K_{n\ast m}$ graphs with $n\ge k$. (Instead of $n\ge k$, one would only need $mn\ge k$, but many papers do not allow small values of n.)

We exhibit the known results on gregarious decompositions of $K_{n\ast m}$ into cycles in

Table 2. Decomposability of $K_{n\ast m}$ into gregarious k-cycles ($n\ge 3$, $m\ge 1$, $k\ge 4$), summary of existence results; G = gregarious, R = resolvable, S = with a specified type of symmetry.

F	n	m	Condition	Properties	References
$C_4$	3	even	–	G	[11]
	≥4	any	$\langle A^{\ast }\rangle$	G	[12,13]
	≥5	even	$\langle A^{\ast }\rangle$	G & S	[13,14]
$C_5$	≥5	any	$\langle A^{\ast }\rangle$	G	[15]
$C_6$	≥6	even	$n\equiv 0,1$ (3)	G	[16]
		any	$\langle A^{\ast }\rangle$	G	[17]
		even	$n\equiv 0$ (3)	G & S	[18]
$C_8$	≥8	any	$\langle A^{\ast }\rangle$	G	[17]
$C_k$	n = k	any (${}^a$)	$2\mid (n-1)m$	G & R	[19]
$C_k$	≡ 0, 1 (mod k)	any	$\langle A^{\ast }\rangle$	G	[20]
$C_k$, $2\nmid k$	any	$k\mid m$	$\langle A^{\ast }\rangle$	G	[20]
$C_k$	odd	$m=k$ prime	n large (${}^b$)	G & S	[15]
$C_k$	even	$m=2k$, k prime	n large (${}^c$)	G & S	[15]
$C_k$, $2\mid k$	$k\mid n$	even	$n>\frac{{(k-1)}^2+3}{4}$	G + S	[21] + [22]
$C_k$, $2\mid k$	$k\mid n-1$	even	–	G & S	[22,23]
$C_k$	even	even	$k=2n-2$	G	[5]
$C_k$	even	$4\mid m$	$k=2n$	G	[5]
$C_k$	$n\mid k$	$\frac{k}{n}\mid m$ (${}^d$)	$2\mid (n-1)m$	G & R & S	Theorem 1

Side conditions: (${}^a$) the combinations $(n,m)=(3,2)$ and $(n,m)=(3,6)$ are excluded; (${}^b$) it is required that n does not have any prime factors smaller than k; (${}^c$) it is required that $n-1$ does not have any prime factors smaller than k, and $n\ge 2k-2$; (${}^d$) if $n=3$, then $mn/k$ is neither 2 nor 6.

. Its first section deals with short cycles $C_k$, for which the problem is completely resolved for all $n\ge k$. The case of 5-cycles was settled by Smith [15]. (To our great surprise, it was explicitly stated and proven (!) in [15] (Lemma 3) that “any integer $k\ge 3$ can be expressed as the sum of three positive integers, $k=k_1+k_2+k_3$, where $k>k_1\ge k_2\ge k_3\ge 1$ and $k_1-k_3\le 1$”.) Several papers have dealt with 6-cycles; after the works by Cho and Gould [16] and by Billington, Smith, and Hoffman [17], more symmetric systems were constructed by Cho [18]. Also, the case of 8-cycles was solved by Billington, Smith, and Hoffman [17]. They proposed the following problem, based on the fact that $\langle A^{\ast }\rangle$ alone is responsible for the existence of gregarious $C_k$-systems in the completely solved cases just listed. Informally, the conjecture states that the relevance of $\langle A^{\ast }\rangle$ remains the same for all cycle lengths, and no additional necessary conditions are needed for any k.

Conjecture 1

([17]). If $K_{n\ast m}$ with $n\ge k$ has an edge decomposition into k-cycles, then it also admits a gregarious $C_k$-decomposition.

In the second section of Table 2, we list classes of cycle lengths k for which positive results are available, but the sufficiency of $\langle A^{\ast }\rangle$ has not yet been proven completely. In the paper on 5-cycles, Smith [15] considered cycles of a general prime length k, as well, assuming that also the vertex classes have the same size k (for n odd) or its double (for n even). In particular, here, the parity of n and m is the same. Interestingly enough, those constructions need an additional number-theoretic assumption on the number n of classes, as indicated in the footnotes of Table 2. It is worth noting that, in the case of odd n and m (i.e., if $|V(K_{n\ast m})|$ is odd), the construction has automorphisms by the simultaneous rotation of vertices inside the classes and, also, by rotation among the classes.

The case where the cycle length equals the number of classes turns out to be easier to handle and admits resolvable decompositions, as proven by Billington, Hoffman, and Rodger [19]. General cycle lengths have also been considered by Smith [20], Kim [21], and Cho [22,23]. A common feature of those results is that, for any fixed k, they provide an infinite family of constructions for every fixed k, allowing arbitrarily large class size m (and also, an arbitrarily large number n of classes, except in [19]).

On the other hand, Cho, Park, and Sano [5] considered cycles longer than n. In their work, cycles of length $2n-2$ deserve special attention, as in the constructed decompositions, some path systems were used, rather than cycle systems. The authors also proposed the following condition stricter than $(\star )$. It is equivalent to (G1) or (G2) if F has at most n vertices and leads to an interesting variant of (G3) if the order of gregarious subgraphs under consideration exceeds the number of vertex classes:

$(\star \star )$

For a subgraph $F\subset K_{n\ast m}$ with k vertices, where $n\ge 2$ and $k\ge 3$, it is required that

$$⌊\frac{k}{n}⌋\le |V(H)\cap V_i|\le ⌈\frac{k}{n}⌉$$

for every $i\in \{1,2,\dots ,n\}$.

Motivated by [5,19], continuing the study of $k>n$, in Section 5 of this paper, we provide resolvable decompositions for an infinite family of triplets $(n,m,k)$ under certain divisibility conditions. The involved subgraphs are gregarious in the stronger sense required by $(\star \star )$. We also extended the methods to obtain resolvable gregarious cycle systems over the combination of lexicographic and direct products of graphs.

Still concerning cycles, there are many publications dealing with decompositions in which more than one cycle length occurs. In a very recent survey [24], Burgess, Danziger, and Traetta summarized the results of that kind and listed 62 reference items. In particular, Section 2.1.2 of that manuscript described a method based on the so-called “row-sum matrices”, by which resolvable gregarious decompositions of $K_{n\ast m}$ and $C_{n\ast m}$ can be generated. The most-related recent works are [25,26,27,28,29,30]. We are grateful to the reviewer for inviting attention to this part of the literature where similar results appeared under an alternative terminology.

Gregarious F-systems for non-cycle graphs F have also been studied to some extent. Supplementing Smith’s theorem [15] on 5-cycles, Fu and Hsu [31] investigated the four connected graphs $F_{5,5}$ different from $C_5$ that have five vertices and five edges. They proved that, for $n\ge 5$ and $m\ge 2$, there exists a gregarious $F_{5,5}$-system over $K_{n\ast m}$ (for each of those four graphs) if and only if $e_{n\ast m}=\frac{1}{2}{m}^{2}n(n-1)$ is a multiple of 5. One crucial point to be emphasized here is that the vertex degrees $(n-1)m$ need not be even (as opposed to the condition $\langle A^{\ast }\rangle$) because all four graphs in question have pendant vertices; hence, the greatest common divisor of the vertex degrees is just 1, rather than 2.

The other non-cycle graph for which gregarious decomposability has been characterized on the class of complete multipartite graphs is the “kite” or “paw” graph on four vertices, obtained from $K_4$ by removing the two edges of a $P_3$ (or attaching a pendant edge to $K_3$). Fu, Hsu, Lo, and Huang [32] proved that, also in this case, $\langle A^{\ast }\rangle$ is necessary and sufficient when $n\ge 4$. This means that m is even or $n\equiv 0,1$ (mod 8). For the same graph, $K_4-E(P_3)$, it was proven by Elakkiya and Muthusamy [33] that the direct product $K_m\times K_n$ of two complete graphs has a gregarious kite factorization if and only if $mn$ is a multiple of four and at least one of m and n is odd.

Finally, we mention that Yücetürk [34] studied gregarious $P_3$-decompositions in graphs $G^f$, obtained from a base graph G equipped with a function $f:V(G)\to \mathbb{N}$, where each vertex v is replaced with an independent set of size $f(v)$.

To the best of our knowledge, gregarious decompositions of vertex-partitioned hypergraphs have not been explored so far. We initiate this open area of research here, and in Section 6, we present the first result of this kind.

5. Blown-Up Cycles and Resolvable Decompositions

In this section, we prove results concerning the existence of decompositions into long cycles. At some points, the following standard terminology will be used. A cycle C in a graph G is called a Hamilton cycle if it contains all vertices of G. A graph G is Hamilton-decomposable if it has an edge decomposition into Hamilton cycles.

A commonly used operation in constructions is the particular case of a lexicographic product, in which an edgeless graph (independent set) is substituted into each vertex. Concerning cycle decompositions, the following principle was stated by Cavenagh and Billington [35] (see, also, [17]) for k even and by Smith [15] for all k: If there exists a (gregarious) k-cycle decomposition of $K_{n\ast m}$, then there exists a (gregarious) k-cycle decomposition of $K_{n\ast tm}$ for every natural number t. Combining this general approach with more-explicit conditions, more symmetry properties of the resulting structures will be obtained, and the existence of decompositions into a wider class of cycles will be derived.

Next, we prove the following result.

Theorem 1.

Let $k,m,n$ be natural numbers such that $(n-1)m$ is even, $n\ge 3$; moreover, k is a multiple of n, and m is a multiple of $k/n$:

$(i)$

If m is odd, then $K_{n\ast m}$ admits a resolvable gregarious $C_k$-system whose automorphism group has ${\mathbb{Z}}_{n-1}\times {\mathbb{Z}}_{k/n}\times {\mathbb{Z}}_{mn/k}$ as a subgroup.

$(ii)$

If m is even, then $K_{n\ast m}$ admits a resolvable gregarious $C_k$-system unless $n=3$ and $mn/k\in \{2,6\}$.

Proof. 

Let us denote $d=k/n$ and $b=m/(k/n)=mn/k$; hence, $m=bd$. The condition $2\mid (n-1)m$ implies that at least one of $n-1$, b, and d is even. For the vertices of $K_{n\ast m}$, it will be convenient to use a triple indexing, $v_{i,s,t}$, where $i\in {\mathbb{Z}}_{n-1}\cup \{n-1\}$, $s\in {\mathbb{Z}}_b$, and $t\in {\mathbb{Z}}_d$. This representation also expresses how the automorphisms will act on the decomposition in case m is odd. In intermediate steps of the construction, single or double indexing will also be used.

Proof of $(i)$.

Since $(n-1)m$ is even, we have that n is odd whenever m is odd. Note that both b and d are odd in this case, since $m=bd$. We perform a construction in three steps. We first apply the classical result, attributed to Walecki by Lucas in [4], that if n is odd, then $K_n$ is Hamilton-decomposable. More explicitly, we consider the decomposition into the following Hamilton cycles:

$$C^j=v_j{v}_{j+1}{v}_{j-1}{v}_{j+2}{v}_{j-2}{v}_{j+3}\dots v_{j+h-1}{v}_{j-h+1}{v}_{j+h}{v}_{n-1};$$

here $h=(n-1)/2$ and $j=0,1,\dots ,h-1$, the last vertex $v_{n-1}$ remains fixed in all these cycles, and subscript addition is taken modulo $(n-1)$ for all the other vertices. Then, the mapping $\mu :V(K_n)\to V(K_n)$ defined as $\mu (v_{n-1})=v_{n-1}$ and $\mu (v_i)=v_{i+1}$ modulo $(n-1)$ for $i=0,1,\dots ,n-2$ is an automorphism of this decomposition.

Next, each $v_i$ is expanded to a set $\{v_{i,0},\dots ,v_{i,b-1}\}$. This expands each $C^j$ to a graph $G_j\cong C_{n\ast b}$. General resolvable decompositions of $C_{n\ast b}$ were constructed in [19] using two parameters $s_1,s_2$ via orthogonal pairs of quasigroups, whose existence was known from previous literature. Instead of that, here, we give a self-contained explicit description of a one-parameter resolvable system based on ${\mathbb{Z}}_b$, which will guarantee symmetry. (It would not work for an even b.)

Consider any $C^j$; let us denote the cyclic sequence of its vertices as $v_{a_1}{v}_{a_2}\dots v_{a_{n-1}}{v}_{n-1}$. For each $s\in {\mathbb{Z}}_b$, we define the base cycle:

$$C^{j,s}=v_{a_1,0}{v}_{a_2,s}{v}_{a_3,0}{v}_{a_4,s}\dots v_{a_{n-2},0}{v}_{a_{n-1},s}{v}_{n-1,2s}.$$

Observe that the differences between the second indices of any two consecutive vertices take all values from ${\mathbb{Z}}_b$ as s runs over ${\mathbb{Z}}_b$. This fact is obvious between the classes of $a_i$ and $a_{i+1}$ for $i=1,\dots ,n-2$, and, also, between $a_{n-1}$ and $v_{n-1}$; this also is valid between $v_{n-1}$ and $a_1$, where the set $\{b-2s\mid s\in {\mathbb{Z}}_b\}$ is just ${\mathbb{Z}}_b$, because b is odd. As a consequence, the rotation $\rho :s^{\prime }\mapsto s^{\prime }+1(\mathrm{mod}b)$ performed simultaneously for all second indices generates an orbit ${\mathcal{C}}^{j,s}$ of $C^{j,s}$, which consists of b mutually vertex-disjoint n-cycles. Hence, taking the collection $\{{\mathcal{C}}^{j,s}\mid s\in {\mathbb{Z}}_b\}$ of these orbits yields a resolvable $C_n$-decomposition of $C_{n\ast b}$. By construction, ${\mathbb{Z}}_b$ is a subgroup of the automorphism group of this system.

The construction is completed via a second expansion, substituting a set $\{v_{i,s,t}\mid t\in {\mathbb{Z}}_d\}$ of size d for each vertex $v_{i,s}$, which yields $K_{n\ast b}\circ {\overline{K}}_d=K_{n\ast bd}=K_{n\ast m}$. Then, from each n-cycle of the form $v_{a_1,s^{\prime }}{v}_{a_2,s+s^{\prime }}{v}_{a_3,s^{\prime }}{v}_{a_4,s+s^{\prime }}\dots v_{a_{n-2},s^{\prime }}{v}_{a_{n-1},s+s^{\prime }}{v}_{n-1,2s+s^{\prime }}$ (as introduced above), we obtain a subgraph isomorphic to $C_{n\ast d}$. The plan is to choose one of those $C_{n\ast d}$, create a decomposition, say ${\mathcal{F}}_0$, into Hamilton cycles, and copy ${\mathcal{F}}_0$ into all the other $C_{n\ast d}$ subgraphs, using the automorphisms $\mu ,\rho$ on the first and second indices. So, the final point is how a Hamiltonian decomposition is created, for which the rotation $\eta :t^{\prime }\mapsto t^{\prime }+1(\mathrm{mod}d)$ over the third indices is an automorphism.

Recall that also d is odd; hence, analogous to $s\in {\mathbb{Z}}_b$ with respect to b in the second index, we can use $t\in {\mathbb{Z}}_d$ with respect to d in the third index, in order to construct a resolvable decomposition of $C_{n\ast d}$ into $d^2$ cycles of length n. Each resolution class has d cycles. Assume, in general, that one such class consists of the following n-cycles:

$(v_{a_1,s_1,t_1},v_{a_2,s_2,t_2},\dots ,v_{a_{n-1},s_{n-1},t_{n-1}},v_{n-1,s_n,t_n})$,

$(v_{a_1,s_1,t_1+1},v_{a_2,s_2,t_2+1},\dots ,v_{a_{n-1},s_{n-1},t_{n-1}+1},v_{n-1,s_n,t_n+1})$,

⋮

$(v_{a_1,s_1,t_1+d-1},v_{a_2,s_2,t_2+q-1},\dots ,v_{a_{n-1},s_{n-1},t_{n-1}+d-1},v_{n-1,s_n,t_n+d-1})$.

The last edges of these cycles are:

$$v_{a_1,s_1,t_1}{v}_{n-1,s_n,t_n}, v_{a_1,s_1,t_1+1}{v}_{n-1,s_n,t_n+1}, \dots , v_{a_1,s_1,t_1+d-1}{v}_{n-1,s_n,t_n+d-1.}$$

We replace them with:

$$v_{a_1,s_1,t_1}{v}_{n-1,s_n,t_n+1}, v_{a_1,s_1,t_1+1}{v}_{n-1,s_n,t_n+2, \dots , }{v}_{a_1,s_1,t_1+d-1}{v}_{n-1,s_n,t_n}$$

in all cycles of the decomposition, performed for the corresponding values of the indices in each cycle. This modification means just rotations on the edge set, namely on the edges between the vertex classes obtained from $v_{a_1,s_1}$ and $v_{n-1,s_n}$ (where $a_1,s_1,s_n$ also depend on the cycle under consideration). Hence, another decomposition is obtained, while the d cycles of length n in each resolution class are modified to one cycle of length $dn$. Observe further that $\eta$ remains an automorphism of the system. This completes the proof of Part $(i)$.

Proof of $(ii)$ for $n\ge 3$.

If m is even, then the structure of constructions is less transparent. In this case, we first apply the Billington–Hoffman–Rodger Theorem [19] (see Table 2) for cycle length n in the graph $K_{n\ast b}$, where $b=mn/k$. This yields a resolvable $C_n$-decomposition with $b^2$ cycles and b resolution classes. The excluded cases $mn/k=2$ and $mn/k=6$ arise from the fact that the constructions for $n=3$ apply two orthogonal Latin squares, which do not exist in those cases. (The existence of two orthogonal Latin squares is highly nontrivial when the order is the double of an odd integer. The history of this problem over the centuries is discussed on page 12 of [3]. The final solution was achieved by Bose, Shrikhande, and Parker in [36].) For all odd $n\ge 5$, alternative constructions are provided in [19] for $b=2$ and $b=6$, as well; the cases of even $n\ge 4$ are handled by a different method.

Once a resolvable $C_n$-decomposition of $K_{n\ast b}$ is at hand, we substitute a set of size d for each vertex. Then, each $C_n$ is expanded to a copy of $C_{n\ast d}$, and those copies form a resolvable $C_{n\ast d}$-decomposition of $K_{n\ast bd}=K_{n\ast m}$. Now, we apply a result of Hetyei [37] and Laskar [38], who proved that $C_{n\ast d}$ is Hamilton-decomposable. In this way, the cycles of each resolution class in the $C_n$-decomposition of $K_{n\ast b}$ yield d resolution classes for a decomposition of $K_{n\ast bd}=K_{n\ast m}$ into cycles $C_{dn}=C_k$. □

A similar theorem on resolvable gregarious decomposability can be proven for the combination of the two graph products ∘ and × also. For the proof, we apply the following important results.

Theorem 2.

Let $n\ge 3$ and $m\ge 1$ be any integers:

$(i)$

(Bermond [39]) If two graphs G and H are Hamilton-decomposable and at least one of them has odd order, then their direct product $G\times H$ is Hamilton-decomposable, as well.

$(ii)$

(Baranyai and Szász [40]) If two graphs G and H are Hamilton-decomposable, then their lexicographic product $G\circ H$ is Hamilton-decomposable, as well.

Now, an extension of Theorem 1 can be stated as follows.

Theorem 3.

Let $G_1,\dots ,G_{\ell }$$(\ell \ge 2)$ be Hamilton-decomposable graphs of odd orders, $n={\prod }_{i=1}^{\ell }\left|V(G_i)\right|$, and let k, m be natural numbers. Let further $G=G_1{\otimes }_1{G}_2{\otimes }_2\cdots {\otimes }_{\ell -1}{G}_{\ell }$, where ${\otimes }_1,\dots ,{\otimes }_{\ell -1}\in \{\circ ,\times \}$ (any sequence of ∘ and ×). If k is a multiple of n and m is a multiple of $k/n$, then the graph $G\circ {\overline{K}}_m$ admits a resolvable gregarious $C_k$-system.

The same conclusion holds if some of the $G_i$ have even orders, but m is even and if ${\otimes }_i=\times$ and $|V(G_i)|$ is even, then all the $|V(G_j)|$ with $j>i$ are odd.

Proof. 

By assumption, every $G_i$ is Hamilton-decomposable. First, we prove by backward induction on $i=\ell -1,\ell -2,\dots ,1$, for both parts of the theorem, that each $H_i:=G_i{\otimes }_i{G}_{i+1}{\otimes }_{i+1}\cdots {\otimes }_{\ell -1}{G}_{\ell }$ is also Hamilton-decomposable. This requirement is satisfied by $H_{\ell }=G_{\ell }$, by assumption. Assume that $H_{i+1}$ is Hamilton-decomposable for a certain i. If ${\otimes }_i=\circ$, then the Baranyai–Szász theorem directly implies that $H_i=G_i{\otimes }_i{H}_{i+1}$ is Hamilton-decomposable, as well. If ${\otimes }_i=\times$, then we observe that at least one of $G_i$ and $H_{i+1}$ has odd order. This is obvious if all $|V(G_j)|$ are odd; it also follows from the parity condition associated with ${\otimes }_i$ in the second part of the theorem if some of the $|V(G_j)|$ are even. Consequently, we can apply Bermond’s theorem to derive the claimed conclusion that $G=G_1{\otimes }_1\cdots {\otimes }_{\ell -1}{G}_{\ell }$ has a decomposition into cycles $C_n$.

The $C_n$-decomposition of G yields a decomposition of $G\circ {\overline{K}}_m$ into edge-disjoint copies of $C_{n\ast m}$. Note that the vertex classes in any of those $C_{n\ast m}$ are the same as in G. Moreover, $(n-1)m$ is even, because, by assumption, either all $|V(G_i)|$ are odd and, thus, also n is odd or, else, m is even. So, the conditions of Theorem 1 are satisfied, and the methods in its proof can be applied. It follows, in particular, that each copy of $C_{n\ast m}$ in the decomposition of $G\circ {\overline{K}}_m$ admits a resolvable decomposition into gregarious k-cycles. The union of its resolution classes provides a decomposition of $G\circ {\overline{K}}_m$ with the required properties. This completes the proof of the theorem. □

6. Gregarious Decompositions of Hypergraphs

In this section, we introduce the generalization of gregarious decompositions from graphs to hypergraphs and carry out its study in the first nontrivial particular case. The terminology and notation needed for our discussion is given below; for a general reference on the theory of hypergraphs, we cite the classical monograph [41].

A hypergraph $H=(V,E)$ has a finite vertex set V and a collection E of nonempty subsets of V called edges. In analogy with Definition 4 on graphs, a decomposition of hypergraph H is an edge-disjoint collection of subhypergraphs $F_1,\dots ,F_s$ of H, whose union is H. Similarly, an F-decomposition—where F is a specified hypergraph—is a decomposition such that each $F_i$ is isomorphic to F. If a vertex partition $(V_1,\dots ,V_n)$ on V is given, then the definition $(\star )$ of gregarious decomposition extends to hypergraphs in a natural way, requiring that each $F_j$ either meets all $V_i$ or, if F has fewer than n vertices, then all vertices of each $F_j$ belong to mutually distinct vertex classes $V_i$. In this context, the following general problem arises.

Problem 1.

For a specified hypergraph F, give sufficient conditions for classes of hypergraphs H to admit a gregarious F-decomposition.

It is also natural to introduce the stricter version $(\star \star )$ of gregarious decompositions for hypergraphs as well. In our case, however, the order of the considered F will be smaller than n; therefore, the two conditions $(\star )$ and $(\star \star )$ will coincide. In the next definition, we collect notation for particular types of hypergraphs for which we will give a solution in this section.

Definition 7.

Let $r\ge 3$, $n\ge r$, and $m\ge 1$ be natural numbers:

$(i)$

The complete r-uniform hypergraph $K_n^{(r)}$ of order n has an n-element vertex set, and its edge set consists of the r-element sets of vertices.

$(ii)$

The vertex set of the hypergraph $K_{n\ast m}^{(r)}$ is $V_1\cup \cdots \cup V_n$, where $|V_i|=m$ for all $1\le i\le n$ and $V_i\cap V_j=⌀$ for all $1\le i<j\le n$; the edges of $K_{n\ast m}^{(r)}$ are those r-element subsets of $V_1\cup \cdots \cup V_n$ that have at most one vertex in each $V_i$.

$(iii)$

The three-uniform hypergraph $H_2^{(3)}$ has four vertices and two three-element edges; i.e., it is isomorphic to the hypergraph that has vertex set $\{a,b,c,d\}$ and edge set $\{abc,abd\}$.

In this section, we concentrate on gregarious $H_2^{(3)}$-decompositions of $K_{n\ast m}^{(3)}$. For any r, each edge of $K_n^{(r)}$ gives rise to $m^r$ edges of $K_{n\ast m}^{(r)}$. In particular, the edge set of $K_{n\ast m}^{(3)}$ consists of $m^3\left(\genfrac{}{}{0pt}{}{n}{3}\right)$ vertex triples. Concerning $m=1$, it was proven by Bermond, Germa, and Sotteau [42] that $K_n^{(3)}$ admits a $H_2^{(3)}$-decomposition if and only if $\left(\genfrac{}{}{0pt}{}{n}{3}\right)$ is even, i.e., if and only if $n\equiv 0,1,2$ (mod 4). Recently, in connection with “mixed hypergraph colorings” (cf., the monograph [43]), various new constructions of $H_2^{(3)}$-systems over $K_n^{(3)}$ and, more generally, over $K_{n\ast m}^{(3)}$ were designed by Bonacini and Marino in [44,45] and by Bonacini, Gionfriddo, and Marino in [46]. Those decompositions of $K_{n\ast m}^{(3)}$ enjoy several nice combinatorial properties, but they are not gregarious in general. In the following result, we characterize the $K_{n\ast m}^{(3)}$ hypergraphs that have gregarious $H_2^{(3)}$-decompositions.

Theorem 4.

For two integers $n\ge 4$ and $m\ge 1$, the hypergraph $K_{n\ast m}^{(3)}$ admits a gregarious $H_2^{(3)}$-decomposition if and only if $\left(\genfrac{}{}{0pt}{}{n}{3}\right)$ or m is even, i.e., either $n\equiv 0,1,2(\mathrm{mod}4)$ or $n\equiv 3(\mathrm{mod}4)$ and m is even.

Proof. 

For the existence of any decomposition into copies of $H_2^{(3)}$, the number of edges has to be even. In the case of $K_{n\ast m}^{(3)}$, this means $2\mid m^3\left(\genfrac{}{}{0pt}{}{n}{3}\right)$; hence, the conditions given in the theorem are necessary.

To prove sufficiency, assume first that $n\equiv 0,1,2$ (mod 4). Then, we can start with an $H_2^{(3)}$-decomposition of $K_n^{(3)}$, say $\mathcal{F}$, as constructed in [42]. Let $abc,abd$ be the two edges in a copy F of $H_2^{(3)}$ in $\mathcal{F}$. Moving from $K_n^{(3)}$ to $K_{n\ast m}^{(3)}$, the vertices $a,b,c,d$ of F are expanded to m-element sets of vertices $a_i,b_i,c_i,d_i$ ($i=1,\dots ,m$). Now, we define the collection (*m) as below:

$$\{\{a_p{b}_q{c}_r,a_p{b}_q{d}_r\}\mid 1\le p,q,r\le m\}$$

of $m^3$ copies of $H_2^{(3)}$. Performing this for every $F\in \mathcal{F}$, a gregarious decomposition of $K_{n\ast m}^{(3)}$ is obtained.

In the rest of the proof, we have to construct systems for $n\equiv 3$ (mod 4). Then, m is even; we first consider the smallest particular case, $m=2$. Let the vertex classes of $K_{n\ast 2}^{(3)}$ be $V_i=\{x_i,y_i\}$ for $i=1,\dots ,4k+3$. We set $V^{\prime }={\bigcup }_{i=1}^{4k}{V}_i$ and $V^{\prime \prime }=V_{4k+1}\cup V_{4k+2}\cup V_{4k+3}$. Here, $|V^{\prime }|$ is a multiple of four; hence, the edges inside $V^{\prime }$ can be decomposed into a gregarious $H_2^{(3)}$-system as above. There remain to decompose three further types of edges:

(a)

The eight edges inside $V^{\prime \prime }$; these are the vertex triples in $V_{4k+1}\times V_{4k+2}\times V_{4k+3}$;

(b)

The $12|V^{\prime }|=96k$ edges with one vertex in $V^{\prime }$ and two vertices in $V^{\prime \prime }$, containing a vertex pair from $(V_{4k+1}\times V_{4k+2})\cup (V_{4k+1}\times V_{4k+3})\cup (V_{4k+2}\times V_{4k+3})$;

(c)

The $\left(\left(\genfrac{}{}{0pt}{}{|V^{\prime }|}{2}\right)-4k\right)|V^{\prime \prime }|=4\left(\genfrac{}{}{0pt}{}{4k}{2}\right)\left|V^{\prime \prime }\right|=48k(4k-1)$ edges with two vertices in distinct parts $V_i,V_j$ of $V^{\prime }$ ($1\le i<j\le 4k$) and one vertex in $V^{\prime \prime }$, which means four possible vertex pairs from $V_i\times V_j$ for each of the $\left(\genfrac{}{}{0pt}{}{4k}{2}\right)$ choices of $i,j$, together with any one of the six vertices from $V^{\prime \prime }$.

The set of edges described in (c) can be decomposed separately from the other two types, defining three pairs of edges for each relevant vertex pair $v_i,v_j$ from $V^{\prime }$ as follows:

$$\{v_i{v}_j{x}_{4k+1},v_i{v}_j{y}_{4k+2}\},\{v_i{v}_j{x}_{4k+2},v_i{v}_j{y}_{4k+3}\},\{v_i{v}_j{x}_{4k+3},v_i{v}_j{y}_{4k+1}\}.$$

These three copies of $H_2^{(3)}$ are taken for all $v_i\in \{x_i,y_i\}$ and $v_j\in \{x_j,y_j\}$, $1\le i<j\le 4k$. Further, the eight edges from (a) can be paired with eight edges from (b), which meet the first vertex class $V_1$:

$$\{v_{4k+1}{v}_{4k+2}{x}_1,v_{4k+1}{v}_{4k+2}{x}_{4k+3}\},\{v_{4k+1}{v}_{4k+2}{y}_1,v_{4k+1}{v}_{4k+2}{y}_{4k+3}\},$$

and these are taken for all the four combinations of $v_{4k+1}\in \{x_{4k+1},y_{4k+1}\}$ and $v_{4k+2}\in \{x_{4k+2},y_{4k+2}\}$. The other edges containing such a pair $\{v_{4k+1},v_{4k+2}\}$ can be decomposed into $4k-1$ copies of $H_2^{(3)}$ as

$$\{v_{4k+1}{v}_{4k+2}{x}_i,v_{4k+1}{v}_{4k+2}{y}_j\}$$

where $(x_i,y_j)\in \{(x_2,y_3),(x_3,y_4),\dots ,(x_{4k-1},y_{4k}),(x_{4k},y_2)\}$. The rest consists of the edges that have one vertex in each of the three sets $V^{\prime }$, $V_{4k+1}\cup V_{4k+2}$ and $V_{4k+3}$. Then, for every $v_0\in V_{4k+1}\cup V_{4k+2}$ and $v_{4k+3}\in V_{4k+3}$ and for all odd $i=1,3,\dots ,4k-1$, we take the following two copies of $H_2^{(3)}$:

$$\{v_0{v}_{4k+3}{x}_i,v_0{v}_{4k+3}{x}_{i+1}\},\{v_0{v}_{4k+3}{y}_i,v_0{v}_{4k+3}{y}_{i+1}\}.$$

In this way, a gregarious $H_2^{(3)}$-decomposition is obtained for $m=2$.

Finally, if m is even and $m>2$, we begin with a gregarious $H_2^{(3)}$-decomposition of $K_{n\ast 2}^{(3)}$ just constructed and proceed analogously in the way as we did during the transformation $K_n^{(3)}\to K_{n\ast m}^{(3)}$ for $n\equiv 0,1,2$ (mod 4). The difference is that, in the present case, each vertex of $K_{n\ast 2}^{(3)}$ will be expanded to a set of $m/2$ vertices. So, the subscripts $p,q,r$ of $(\ast m)$ now range between 1 and $m/2$. Then, each copy of $H_2^{(3)}$ in $K_{n\ast 2}^{(3)}$ gives rise to $m^3/8$ copies of $H_2^{(3)}$ to form a gregarious decomposition of $K_{n\ast m}^{(3)}$. □

7. Discussion

Decomposition techniques are very important in both theory and practice. In this paper, we considered “gregarious decompositions” of graphs and hypergraphs. This research established a link between partitions of the edge set and a fixed partition of the vertex set, requiring that each sub(hyper)graph in the decomposition meets as many classes of the given vertex partition as possible. In Section 4, we gave a detailed survey of the existing literature on the subject.

In Section 5, we proved the decomposability into relatively long gregarious cycles, for complete equipartite graphs (Theorem 1) and, more generally, for graph classes obtained by two types of product operations, where the two types may occur simultaneously (Theorem 3). Our new results provide extensions of some of the known theorems in various directions concerning gregarious decompositions: (1) further types of subgraphs, (2) the existence of resolution classes, (3) guaranteed types of symmetry, and (4) larger classes of host graphs. Each of these four offer much space for further research.

In Section 6, we initiated the analogous problem for hypergraphs and achieved the first result of that kind. We solved the design-theoretical spectrum problem for the gregarious decomposability of complete equipartite three-uniform hypergraphs into subhypergraphs of order four with two edges. Our Theorem 4 is just the first step on a long way, opening a wide area for future studies. All four aspects, just mentioned concerning Section 5, would be of definite interest to explore on hypergraphs as well. What is more, in hypergraphs, many further types of properties are worth taking into consideration. One example from the cited papers [45,46] is the class of edge-balanced decompositions. Higher degrees of balance may also occur in decompositions of hypergraphs where the size of edges is larger than three.