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]

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
[7]

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
[8]

Yanjun He, Wei Zeng, Minghui Yu, Hongtao Zhou, Delie Ming. Incentives for production capacity improvement in construction supplier development. Journal of Industrial & Management Optimization, 2021, 17 (1) : 409-426. doi: 10.3934/jimo.2019118
[9]

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
[10]

Taofeng Ye, Yan Zhao. Quality choice and capacity rationing in advance selling. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020107
[11]

Rongrong Jin, Guangcun Lu. Representation formula for symmetrical symplectic capacity and applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (8) : 4705-4765. doi: 10.3934/dcds.2020199
[12]

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
[13]

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
[14]

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
[15]

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
[16]

Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011
[17]

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
[18]

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
[19]

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
[20]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences