On the Shannon capacity of a directed graph (Q1074597): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Henri Meyniel / rank | |||
Property / reviewed by | |||
Property / reviewed by: Peter Horák / rank | |||
Property / author | |||
Property / author: Henri Meyniel / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Peter Horák / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Shannon capacity of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4194987 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a Problem of C. E. Shannon in Graph Theory / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0195-6698(85)80042-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2044301127 / rank | |||
Normal rank |
Latest revision as of 08:29, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Shannon capacity of a directed graph |
scientific article |
Statements
On the Shannon capacity of a directed graph (English)
0 references
1985
0 references
The Shannon capacity of an undirected graph G, t(G), is \(t(G)=\sup^ k\sqrt{\alpha (G^ k)}\), \(k\in N\), where \(\alpha\) (G) is the vertex independence number of G and \(G^ k\) the Cartesian product of G by itself k times. The authors extend naturally the definition for directed graphs and show that if G is a directed cycle of length n then \(t(G)=n-1\) and \(t(G)=| V(G)|\) for every cycle-free digraph G.
0 references
Shannon capacity
0 references
directed graphs
0 references
directed cycle
0 references
digraph
0 references