DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Dilbarjot

Dilbarjot

The University of Winnipeg

email: dilbarjot@uwinnipeg.ca

S. Dueck (Gosselin)

Shonda Marie Dueck (Gosselin)

Department of Mathematics and Statistics,
University of Winnipeg

email: s.gosselin@uwinnipeg.ca

Title:

Cyclic partitions of complete and almost complete uniform hypergraphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 747-758

Received: 2019-08-31 , Revised: 2020-01-11 , Accepted: 2020-01-13 , Available online: 2020-02-14 , https://doi.org/10.7151/dmgt.2303

Abstract:

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.

Keywords:

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

References:

  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 $K_n-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
Close