Geodesic
Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 747-758.

Voir la notice de l'article provenant de la source Library of Science

We consider cyclic partitions of the complete k-uniform hypergraph on a finite set V, minus a set of s edges, s ≥ 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 θ∈ Sym(V) such that the sets E, E^θ, E^{θ^2, . . ., E^θ^t−1 partition the set of all k-subsets of V minus a set of s edges. Such a permutation θ 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^α-complementary k-hypergraph of order n, where p is prime, s= Π_i ≥ 0 n_ik_i, and n_i and k_i are the entries in the base-p^α 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^α-complementary k-hypergraph, and the equivalence of these two conditions yield an interesting relationship between the base-p representation and the base-p^α 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.
Keywords: almost self-complementary hypergraph, uniform hypergraph, cyclically t -complementary hypergraph, ( t,k )-complementing permutation 
@article{DMGT_2022_42_3_a3,
     author = {Dilbarjot and Gosselin, Shonda Dueck},
     title = {Cyclic {Partitions} of {Complete} and {Almost} {Complete} {Uniform} {Hypergraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {747--758},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a3/}
}
TY  - JOUR
AU  - Dilbarjot
AU  - Gosselin, Shonda Dueck
TI  - Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 747
EP  - 758
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a3/
LA  - en
ID  - DMGT_2022_42_3_a3
ER  - 
%0 Journal Article
%A Dilbarjot
%A Gosselin, Shonda Dueck
%T Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 747-758
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a3/
%G en
%F DMGT_2022_42_3_a3
Dilbarjot; Gosselin, Shonda Dueck. Cyclic Partitions of Complete and Almost Complete Uniform Hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 747-758. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a3/

[1] L. Adamus, B. Orchel, A. Szymański, P. Wojda and M. Zwonek, A note on t-complementing permutations for graphs, Inform. Process. Lett. 110 (2009) 44–45. https://doi.org/10.1016/j.ipl.2009.10.004

[2] J.M. Bernaldez, On k-complementing permutations of cyclically k-complementary graphs, Discrete Math. 151 (1996) 67–70. https://doi.org/10.1016/0012-365X(94)00082-T

[3] C.R.J. Clapham, Graphs self-complementary in Kn − e, Discrete Math. 81 (1990) 229–235. https://doi.org/10.1016/0012-365X(90)90062-M

[4] M.J. Colbourn and C.J. Colbourn, Graph isomorphism and self-complementary graphs, ACM SIGACT News 10 (1978) 25–29. https://doi.org/10.1145/1008605.1008608

[5] K.S. Davis and W.A. Webb, Lucas’ theorem for prime powers, European J. Combin. 11 (1990) 229–233. https://doi.org/10.1016/S0195-6698(13)80122-9

[6] A. Farrugia, Self-Complementary Graphs and Generalizations: a Comprehensive Reference Manual, Master’s Thesis (University of Malta, 1999).

[7] S. Gosselin, Almost t-complementary uniform hypergraphs, Aequationes Math. 93 (2019) 1177–1182. https://doi.org/10.1007/s00010-018-0631-y

[8] S. Gosselin, Cyclically t-complementary uniform hypergraphs, European J. Combin. 31 (2010) 1629–1636. https://doi.org/10.1016/j.ejc.2010.05.001

[9] S. Gosselin, Generating self-complementary uniform hypergraphs, Discrete Math. 310 (2010) 1366–1372. https://doi.org/10.1016/j.disc.2010.01.003

[10] L.N. Kamble, C.M. Deshpande and B.Y. Bam, Almost self-complementary 3 -uniform hypergraphs, Discuss. Math. Graph Theory 37 (2017) 131–140. https://doi.org/10.7151/dmgt.1919

[11] E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852) 93–146. https://doi.org/10.1515/crll.1852.44.93

[12] É. Lucas, Sur les congruences des nombres eulériens et les coefficients différentiels des functions trigonométriques suivant un module premier, Bull. Soc. Math. France 6 (1878) 49–54.

[13] G. Ringel, Selbstkomplementäre graphen, Arch. Math. (Basel) 14 (1963) 354–358. https://doi.org/10.1007/BF01234967

[14] H. Sachs, Über selbstkomplementäre graphen, Publ. Math. Debrecen 9 (1962) 270–288.

[15] D.A. Suprunenko, Self-complementary graphs, Cybernet. Systems Anal. 21 (1985) 559–567. https://doi.org/10.1007/BF01074707

[16] A. Szymański and A.P. Wojda, Cyclic partitions of complete uniform hypergraphs, Electron. J. Combin. 17 (2010) #R118. https://doi.org/10.37236/390

[17] A. Szymański and A.P. Wojda, Self-complementing permutations of k-uniform hypergraphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 117–123.

[18] A. Szymański, A note on self-complementary 4 -uniform hypergraphs, Opuscula Math. 25 (2005) 319–323.

[19] A. Szymański and A.P.Wojda, A note on k-uniform self-complementary hypergraphs of given order, Discuss. Math. Graph Theory 29 (2009) 199–202. https://doi.org/10.7151/dmgt.1440

[20] A.P. Wojda, Almost self-complementary uniform hypergraphs, Discuss. Math. Graph Theory 38 (2018) 607–610. https://doi.org/10.7151/dmgt.2028

[21] A.P. Wojda, Self-complementary hypergraphs, Discuss. Math. Graph Theory 26 (2006) 217–224. https://doi.org/10.7151/dmgt.1314