Sperner capacity of small digraphs

Pages: 125 - 133, Volume 3, Issue 2, May 2009

doi:10.3934/amc.2009.3.125       Abstract        Full Text (162.3K)       Related Articles

Lasse Kiviluoto - Celtius Ltd, Pieni Roobertinkatu 11, 00130 Helsinki, Finland (email)
Patric R. J. Östergård - Department of Communications and Networking, Helsinki University of Technology TKK, P.O. Box 3000, 02015 TKK, Finland (email)
Vesa P. Vaskelainen - Department of Communications and Networking, Helsinki University of Technology TKK, P.O. Box 3000, 02015 TKK, Finland (email)

Abstract: The classical concept of Shannon capacity of undirected graphs was extended by Gargano, Körner, and Vaccaro to digraphs in the early 1990s, and termed Sperner capacity. Shannon, in his seminal work, determined the capacities for all isomorphism classes of undirected graphs with up to five vertices, except for the 5-cycle, which was finally settled by Lovász in 1979. The work of Shannon is here paralleled for digraphs; the Sperner capacity is determined for all but 8 of the 9846 isomorphism classes of digraphs with at most 5 vertices.

Keywords:  Digraph, Shannon capacity, Sperner capacity, zero-error capacity.
Mathematics Subject Classification:  Primary: 94A24; Secondary: 05C20.

Received: November 2008;      Revised: March 2009;      Published: May 2009.