Self-complementary hypergraphs
A. Paweł Wojda
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 217-224 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A k-uniform hypergraph H = (V;E) is called self-complementary if there is a permutation σ:V → V, called self-complementing, such that for every k-subset e of V, e ∈ E if and only if σ(e) ∉ E. In other words, H is isomorphic with H'=(V;Vk-E). In the present paper, for every k, (1 ≤ k ≤ n), we give a characterization of self-complementig permutations of k-uniform self-complementary hypergraphs of the order n. This characterization implies the well known results for self-complementing permutations of graphs, given independently in the years 1962-1963 by Sachs and Ringel, and those obtained for 3-uniform hypergraphs by Kocay, for 4-uniform hypergraphs by Szymański, and for general (not uniform) hypergraphs by Zwonek.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270729 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1314,
     author = {A. Pawe\l\ Wojda},
     title = {Self-complementary hypergraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {217-224},
     zbl = {1142.05058},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1314}
}

A. Paweł Wojda. Self-complementary hypergraphs. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 217-224. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1314/

[000] [1] A. Benhocine and A.P. Wojda, On self-complementation, J. Graph Theory 8 (1985) 335-341, doi: 10.1002/jgt.3190090305. | Zbl 0587.05054

[001] [2] W. Kocay, Reconstructing graphs as subsumed graphs of hypergraphs, and some self-complementary triple systems, Graphs and Combinatorics 8 (1992) 259-276, doi: 10.1007/BF02349963. | Zbl 0759.05064

[002] [3] G. Ringel, Selbstkomplementäre Graphen, Arch. Math. 14 (1963) 354-358, doi: 10.1007/BF01234967.

[003] [4] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962) 270-288. | Zbl 0119.18904

[004] [5] A. Szymański, A note on self-complementary 4-uniform hypergraphs, Opuscula Mathematica 25/2 (2005) 319-323. | Zbl 1122.05067

[005] [6] M. Zwonek, A note on self-complementary hypergraphs, Opuscula Mathematica 25/2 (2005) 351-354. | Zbl 1122.05068