American Institute of Mathematical Sciences

Advanced
May  2009, 3(2): 125-133. doi: 10.3934/amc.2009.3.125

Sperner capacity of small digraphs

Lasse Kiviluoto 1, , Patric R. J. Östergård 2, and  Vesa P. Vaskelainen 2,

1. 

Celtius Ltd, Pieni Roobertinkatu 11, 00130 Helsinki, Finland
2. 

Department of Communications and Networking, Helsinki University of Technology TKK, P.O. Box 3000, 02015 TKK, Finland, Finland

Received  November 2008 Revised  March 2009 Published  May 2009

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: zero-error capacity., Shannon capacity, Digraph, Sperner capacity.
Mathematics Subject Classification: Primary: 94A24; Secondary: 05C2.
Citation: Lasse Kiviluoto, Patric R. J. Östergård, Vesa P. Vaskelainen. Sperner capacity of small digraphs. Advances in Mathematics of Communications, 2009, 3 (2) : 125-133. doi: 10.3934/amc.2009.3.125
[1]

Kai Zehmisch. The codisc radius capacity. Electronic Research Announcements, 2013, 20: 77-96. doi: 10.3934/era.2013.20.77
[2]

Benny Avelin, Tuomo Kuusi, Mikko Parviainen. Variational parabolic capacity. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 5665-5688. doi: 10.3934/dcds.2015.35.5665
[3]

Chungen Liu, Qi Wang. Symmetrical symplectic capacity with applications. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2253-2270. doi: 10.3934/dcds.2012.32.2253
[4]

Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060
[5]

Jie Xiao. On the variational $p$-capacity problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (3) : 959-968. doi: 10.3934/cpaa.2015.14.959
[6]

Jianbin Li, Ruina Yang, Niu Yu. Optimal capacity reservation policy on innovative product. Journal of Industrial & Management Optimization, 2013, 9 (4) : 799-825. doi: 10.3934/jimo.2013.9.799
[7]

Qing Yang, Shiji Song, Cheng Wu. Inventory policies for a partially observed supply capacity model. Journal of Industrial & Management Optimization, 2013, 9 (1) : 13-30. doi: 10.3934/jimo.2013.9.13
[8]

Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449
[9]

François Blanchard, Wen Huang. Entropy sets, weakly mixing sets and entropy capacity. Discrete & Continuous Dynamical Systems - A, 2008, 20 (2) : 275-311. doi: 10.3934/dcds.2008.20.275
[10]

Lizhong Peng, Shujun Dang, Bojin Zhuang. Localization operator and digital communication capacity of channel. Communications on Pure & Applied Analysis, 2007, 6 (3) : 819-827. doi: 10.3934/cpaa.2007.6.819
[11]

Peter Hinow, Ami Radunskaya. Ergodicity and loss of capacity for a random family of concave maps. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2193-2210. doi: 10.3934/dcdsb.2016043
[12]

Adriano Festa, Simone Göttlich, Marion Pfirsching. A model for a network of conveyor belts with discontinuous speed and capacity. Networks & Heterogeneous Media, 2019, 14 (2) : 389-410. doi: 10.3934/nhm.2019016
[13]

Oliver Kolb, Simone Göttlich, Paola Goatin. Capacity drop and traffic control for a second order traffic model. Networks & Heterogeneous Media, 2017, 12 (4) : 663-681. doi: 10.3934/nhm.2017027
[14]

Wei Liu, Shiji Song, Ying Qiao, Han Zhao. The loss-averse newsvendor problem with random supply capacity. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1417-1429. doi: 10.3934/jimo.2016080
[15]

Boris Andreianov, Carlotta Donadello, Ulrich Razafison, Massimiliano D. Rosini. Riemann problems with non--local point constraints and capacity drop. Mathematical Biosciences & Engineering, 2015, 12 (2) : 259-278. doi: 10.3934/mbe.2015.12.259
[16]

Bogdan Kwiatkowski, Tadeusz Kwater, Anna Koziorowska. Influence of the distribution component of the magnetic induction vector on rupturing capacity of vacuum switches. Conference Publications, 2011, 2011 (Special) : 913-921. doi: 10.3934/proc.2011.2011.913
[17]

Jianhong Wu, Ruyuan Zhang. A simple delayed neural network with large capacity for associative memory. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 851-863. doi: 10.3934/dcdsb.2004.4.851
[18]

Francisco Ortegón Gallego, María Teresa González Montesinos. Existence of a capacity solution to a coupled nonlinear parabolic--elliptic system. Communications on Pure & Applied Analysis, 2007, 6 (1) : 23-42. doi: 10.3934/cpaa.2007.6.23
[19]

J. X. Velasco-Hernández, M. Núñez-López, G. Ramírez-Santiago, M. Hernández-Rosales. On carrying-capacity construction, metapopulations and density-dependent mortality. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1099-1110. doi: 10.3934/dcdsb.2017054
[20]

M. M. Cavalcanti, V.N. Domingos Cavalcanti, D. Andrade, T. F. Ma. Homogenization for a nonlinear wave equation in domains with holes of small capacity. Discrete & Continuous Dynamical Systems - A, 2006, 16 (4) : 721-743. doi: 10.3934/dcds.2006.16.721

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences