On the Shannon capacity of a directed graph
type: Item
instance of: scholarly article
title: On the Shannon capacity of a directed graph
zbMATH Open document ID: 0591.05034
DOI: 10.1016/S0195-6698(85)80042-1
author: E. Bidamon
author: Henri Meyniel
published in: European Journal of Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3948304
zbMATH Keywords: Shannon capacity
zbMATH Keywords: directed graphs
zbMATH Keywords: directed cycle
zbMATH Keywords: digraph
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Q5615282
cites work: On the Shannon capacity of a graph
cites work: Q4194987
cites work: On a Problem of C. E. Shannon in Graph Theory
full work available at URL: s0195-6698(85)80042-1
OpenAlex ID: W2044301127
description: scientific article; zbMATH DE number 3948304