ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Dilbarjot and S. Dueck ( Gosselin)


Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs


Discussiones Mathematicae Graph Theory

Received: 2019-08-31, Revised: 2020-01-11, Accepted: 2020-01-13,


We consider cyclic partitions of the complete $k$-uniform hypergraph on a finite set $V$, minus a set of $s$ edges, $s\geq 0$. An $s$-almost $t$-complementary $k$-hypergraph is a $k$-uniform hypergraph with vertex set $V$ and edge set $E$ for which there exists a permutation $\theta\in Sym(V)$ such that the sets $E, E^\theta, E^{\theta^2}, \ldots, E^{\theta^{t-1}}$ partition the set of all $k$-subsets of $V$ minus a set of $s$ edges. Such a permutation $\theta$ is called an $s$-almost $(t,k)$-complementing permutation. The $s$-almost $t$-complementary $k$-hypergraphs are a natural generalization of the almost self-complementary graphs which were previously studied by Clapham, Kamble et al. and Wojda. We prove the existence of an $s$-almost $p^\alpha$-complementary $k$-hypergraph of order $n$, where $p$ is prime, $s = \prod_{i\geq 0}{{n_i}\choose {k_i}}$, and $n_i$ and $k_i$ are the entries in the base-$p^{\alpha}$ representations of $n$ and $k$, respectively. This existence result yields a combinatorial argument which generalizes Lucas' classic 1878 number theory result to prime powers, which was originally proved by Davis and Webb in 1990 by another method. In addition, we prove an alternative statement of the necessary and sufficient conditions for the existence of a $p^{\alpha}$-complementary $k$-hypergraph, and the equivalence of these two conditions yield an interesting relationship between the base-$p$ representation and the base-$p^{\alpha}$ representation of a positive integer $n$. Finally, we determine a set of necessary and sufficient conditions on $n$ for the existence of a $t$-complementary $k$-uniform hypergraph on $n$ vertices for composite values of $t$, extending previous results due to Wojda, Szymański and Gosselin.


almost self-complementary hypergraph, uniform hypergraph, cyclically $t$-complementary hypergraph, $(t,k)$-complementing permutation