Paper Info
Title
Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities
Abstract
We prove 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. This result is used to explore the relation between the Shannon and Sperner capacity of certain graphs. In particular, using results of Lovasz, we show that the maximum Sperner capacity over all orientations of the edges of a vertex-transitive self-complementary graph equals its Shannon capacity. (C) 1999 Academic Press.
Year
DOI
Venue
1999
10.1006/eujc.1998.0256
Eur. J. Comb.
Keywords
DocType
Volume
self-complementary graph,shannon capacity
Journal
20
Issue
ISSN
Citations 
1
0195-6698
11
PageRank 
References 
Authors
1.28
3
2
Name
Order
Citations
PageRank
Attila Sali116624.30
Gábor Simonyi224929.78