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]

Guofen Zhang, Ping Li, Jianfeng Hou, Bo Bai. The zero-error capacity of binary channels with 2-memories. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022009
[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Taofeng Ye, Yan Zhao. Quality choice and capacity rationing in advance selling. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3049-3084. doi: 10.3934/jimo.2020107
[17]

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

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

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

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy