Self-complementary hypergraphs

A. Paweł Wojda

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 2, page 217-224
  • ISSN: 2083-5892

Abstract

top
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 ; V k - 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.

How to cite

top

A. Paweł Wojda. "Self-complementary hypergraphs." Discussiones Mathematicae Graph Theory 26.2 (2006): 217-224. <http://eudml.org/doc/270729>.

@article{A2006,
abstract = {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^\{\prime \} = (V; \binom\{V\}\{k\} - 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.},
author = {A. Paweł Wojda},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-uniform hypergraph; self-complementary hypergraph; -uniform hypergraph},
language = {eng},
number = {2},
pages = {217-224},
title = {Self-complementary hypergraphs},
url = {http://eudml.org/doc/270729},
volume = {26},
year = {2006},
}

TY - JOUR
AU - A. Paweł Wojda
TI - Self-complementary hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 2
SP - 217
EP - 224
AB - 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^{\prime } = (V; \binom{V}{k} - 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.
LA - eng
KW - k-uniform hypergraph; self-complementary hypergraph; -uniform hypergraph
UR - http://eudml.org/doc/270729
ER -

References

top
  1. [1] A. Benhocine and A.P. Wojda, On self-complementation, J. Graph Theory 8 (1985) 335-341, doi: 10.1002/jgt.3190090305. Zbl0587.05054
  2. [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. Zbl0759.05064
  3. [3] G. Ringel, Selbstkomplementäre Graphen, Arch. Math. 14 (1963) 354-358, doi: 10.1007/BF01234967. 
  4. [4] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962) 270-288. Zbl0119.18904
  5. [5] A. Szymański, A note on self-complementary 4-uniform hypergraphs, Opuscula Mathematica 25/2 (2005) 319-323. Zbl1122.05067
  6. [6] M. Zwonek, A note on self-complementary hypergraphs, Opuscula Mathematica 25/2 (2005) 351-354. Zbl1122.05068

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.