Shannon Capacity

Author

Eric W. Weisstein
April 27, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/ShannonCapacity.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/ShannonCapacity.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Known

Empty Graph

According to "perfect graphs have α==Θ, so Θ(n (Subscript[K, 1])) == n

However, according to Θ(K(n,k))=Binomial[n-1,k-1], so Θ(K(n,n-1))=Θ(n (Subscript[K, 1]))==Binomial[n-1,n-2]==n-1

Bottom line:

2(Subscript[K, 1])

GraphStrongProduct[Graph["2K1"],Graph["2K1"]]//RecognizeGraph

((GraphData[{"Empty",4},"IndependenceNumber"])^(1/2))

GraphStrongProduct[GraphStrongProduct[Graph["2K1"],Graph["2K1"]],Graph["2K1"]]//RecognizeGraph

((GraphData[{"Empty",8},"IndependenceNumber"])^(1/3))

3(Subscript[K, 1])

GraphStrongProduct[Graph["3K1"],Graph["3K1"]]//RecognizeGraph

((GraphData[{"Empty",9},"IndependenceNumber"])^(1/2))

GraphStrongProduct[GraphStrongProduct[Graph["3K1"],Graph["3K1"]],Graph["3K1"]]//RecognizeGraph

((GraphData[{"Empty",27},"IndependenceNumber"])^(1/3))

Table

Grid[GraphData[#,{"V","Name","ShannonCapacity"}]&/@SortBy[DeleteCases[GraphData["ShannonCapacity","Defined"],{_Integer,_}],GraphData[#,"V"]&],Frame->All,Alignment->Left]