On the Shannon capacity of a directed graph (Q1074597): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Henri Meyniel / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Peter Horák / rank
 
Normal rank

Revision as of 02:10, 11 February 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
    0 references
    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
    0 references

    Identifiers