Connectivity of Regular Directed Graphs with Small Diameters
- 1 March 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (3) , 267-273
- https://doi.org/10.1109/tc.1985.1676569
Abstract
This paper clarifies the relation between the diameter k and the edge or node connectivity Ce or c,, of digraphs. The following two inequalities are derived: where n is the number of nodes, d is the maximum degree, and d is the minimum degree.Keywords
This publication has 11 references indexed in Scilit:
- Some New Results About the (d, k) Graph ProblemIEEE Transactions on Computers, 1982
- Dense Trivalent Graphs for Processor InterconnectionIEEE Transactions on Computers, 1982
- A Regular Network for Multicomputer SystemsIEEE Transactions on Computers, 1982
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- Distributed fault-tolerance for large multiprocessor systemsPublished by Association for Computing Machinery (ACM) ,1980
- Analysis and Design of Reliable Computer NetworksIEEE Transactions on Communications, 1972
- On the Construction of (d, k) GraphsIEEE Transactions on Electronic Computers, 1965
- Topological constraints on interconnection-limited logicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1964
- AlgebraPublished by Springer Nature ,1964
- Some properties of line digraphsRendiconti del Circolo Matematico di Palermo Series 2, 1960