zbMATH — the first resource for mathematics

An analogue of the Shannon capacity of a graph. (English) Zbl 0717.05070
The Shannon capacity of a graph G is the value \(\alpha_ s(G)=\sup_{n}^ n\sqrt{\alpha (G^ n)}\), where \(\alpha (G^ n)\) is the independence number of the strong product of n copies of G. The independent domination number of G, denoted \({\mathcal K}(G)\), is the smallest possible cardinality of a set which is both independent and dominating. The author introduces an analogue of the Shannon capacity, namely the \({\mathcal K}\)-capacity \({\mathcal K}_ s(G)=\inf_{n}^ n\sqrt{{\mathcal K}(G^ n)}\). Consider the graph \(G_{{\mathcal A}}=(V,E)\) which has one vertex for each letter in an alphabet \({\mathcal A}\) and in which two vertices are adjacent if and only if the corresponding letters can be confused. The Shannon capacity of \(G_{{\mathcal A}}\) yields an upper bound on the cardinality of a set of n-letter words which are pairwise nonconfusable, and the \({\mathcal K}\)-capacity of \(G_{{\mathcal A}}\) yields a lower bound on the size of a maximal such set. The author makes use of linear programming duality to present lower bounds on the \({\mathcal K}\)- capacity and uses them to evaluate the \({\mathcal K}\)-capacity of certain cycles and trees.

05C99 Graph theory
Full Text: DOI
[1] Bondy, J. A.; Murty, U. S. R., Graph theory with applications, (1976) · Zbl 1226.05083
[2] Farber, Martin, Domination and duality in weighted trees, Congr. Numer., 33, 3, (1981) · Zbl 0498.05025
[3] Farber, Martin, Independent domination in chordal graphs, Oper. Res. Lett., 1, 134, (198182) · Zbl 0495.05053
[4] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169, (1981) · Zbl 0557.10036
[5] Hell, P.; Roberts, F. S., Analogues of the Shannon capacity of a graph, Ann. Discrete Math., 12, 155, (1982) · Zbl 0501.05035
[6] Khachian, L. G., A polynomial algorithm in linear programming, Soviet Math. Dokl., 20, 191, (1979) · Zbl 0409.90079
[7] Lovász, László, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, (1979) · Zbl 0395.94021
[8] McEliece, RobertJ.; Posner, EdwardC., Hide and seek, data storage, and entropy, Ann. Math. Statist., 42, 1706, (1971) · Zbl 0235.05001
[9] On strong independence and the strong product of graphsin preparation
[10] Rosenfeld, M., On a problem of C. E. Shannon in graph theory, Proc. Amer. Math. Soc., 18, 315, (1967) · Zbl 0147.42801
[11] Shannon, ClaudeE., The zero error capacity of a noisy channel, Institute of Radio Engineers, Transactions on Information Theory, IT-2, 8, (1956)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.