Shannon Capacity

Let  denote the independence number of a graph . Then the Shannon capacity , sometimes also denoted , of  is defined as

{{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]...□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]G_()_(k))]^(1/k), " src="https://mathworld.wolfram.com/images/equations/ShannonCapacity/NumberedEquation1.svg" style="height:54px; width:216px" />

where {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]" src="https://mathworld.wolfram.com/images/equations/ShannonCapacity/Inline6.svg" style="height:22px; width:14px" /> denoted the graph strong product (Shannon 1956, Alon and Lubetzky 2006). The Shannon capacity is an important information theoretical parameter because it represents the effective size of an alphabet in a communication model represented by a graph  (Alon 1998).

 satisfies

The Shannon capacity is in general very difficult to calculate (Brimkov et al. 2000). In fact, the Shannon capacity of the cycle graph  was not determined as  until 1979 (Lovász 1979), and the Shannon capacity of  is perhaps one of the most notorious open problems in extremal combinatorics (Bohman 2003).

Lovász (1979) showed that the Shannon capacity of the -Kneser graph is , that of a vertex-transitive self-complementary graph (which includes all Paley graphs)  is , and that of the Petersen graph is 4.

All graphs whose Shannon capacity is known attain their capacity either at  (i.e., at their independence number; e.g., perfect graphs),  (e.g., self-complementary vertex-transitive graphs-including the Paley graphs), or else do not attain it at any value of  (e.g., the graph union of the cycle graph  with a singleton graph) (Alon and Lubetzky 2006).

---

REFERENCES

Alon, N. "Explicit Ramsey Graphs and Orthonormal Labelings." Elec. J. Combin. 1, No. R12, 1-8, 1994.

Alon, N. "The Shannon Capacity of a Union." Combinatorica 18, 301-310, 1998.

Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.

Bohman, T. "A Limit Theorem for the Shannon Capacities of Odd Cycles. I." Proc. Amer. Math. Soc. 131, 3559-3569, 2003.

Bohman, T. and Holzman, R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of Odd Cycles." IEEE Trans. Inform. Th. 49, 721-722, 2003.

Brimkov, V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi). Berlin: Springer-Verlag, pp. 291-305, 2000.

Haemers, W. "An Upper Bound for the Shannon Capacity of a Graph." In Algebraic Methods in Graph Theory. Szeged, Hungary: pp. 267-272, 1978.

Haemers, W. "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. 25, 231-232, 1979.Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.

Lovász, L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. IT-25, 1-7, 1979.

Riis, S. "Graph Entropy, Network Coding and Guessing." 27 Nov 2007. http://arxiv.org/abs/0711.4175v1.Schrijver, A. "A Comparison of the Delsarte and Lovász Bounds." IEEE Trans. Inform. Th. 25, 425-429, 1979.

Shannon, C. E. "The Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th. 2, 8-19, 1956.v

an Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الإعلام يشارك في الاجتماع التحضيري لمناقشة الخطة الإعلامية لزيارة عاشوراء

بحضور متوليها الشرعي.. العتبة العباسية المقدسة تواصل إقامة المجالس الحسينية لإحياء شهر المحرم

قسم الشؤون الفكرية يطلق برنامجه التبليغي في أكثر من 20 دولة إفريقية

شعبتا الخطابة النسوية والتوجيه الديني تواصلان إقامة المجالس الحسينية في مرقد أبي الفضل العباس (عليه السلام)

المزيد

الآخبار الصحية

دراسة تكشف علاقة خطيرة بين عمر الأم وصحة مولودها

دراسة تحذر.. اضطراب نوم بسيط قد يسبب الموت المبكر ؟

الاستحمام بالماء الساخن.. راحة مؤقتة وأضرار دائمة للبشرة

ماذا يحدث للجسم عند تخطي وجبة الإفطار؟

المزيد

الآخبار التكنلوجية

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

السد الصيني العملاق يعيق دوران الأرض ويغيّر شكلها ؟

السعودية تطلق 10 تجارب علمية إلى محطة الفضاء الدولية

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength