Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities (Q1279873)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities |
scientific article; zbMATH DE number 1251353
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities |
scientific article; zbMATH DE number 1251353 |
Statements
Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities (English)
0 references
17 February 1999
0 references
The authors show that the edges of a self-complementary graph and its complement can be oriented in such a way that they remain isomorphic as digraphs and their union is a transitive tournament. From this and a result of Lovász they deduce that if \(G\) is a vertex-transitive self-complementary graph, then the maximum Sperner capacity over all orientations of \(G\) equals the Shannon capacity of \(G\).
0 references
digraphs
0 references
tournament
0 references
self-complementary graph
0 references
Sperner capacity
0 references
Shannon capacity
0 references
