On the Invulnerability of the Regular Complete k-Partite Graphs
Authors:
- F. T. BoeschFBF. T. Boesch
- A. FelzerAFA. Felzer
- 1 March 1971
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Mathematics
- Vol. 20 (2) , 176-182
Abstract
The size of the smallest edge cut-set (cohesion) and the size of the smallest node cut-set (connectivity) have been used by some authors as vulnerability measures of a graph. Generalizations of the cohesion and the connectivity are introduced herein as new vulnerability criteria. It is shown that the regular complete k-partite graph is optimal with respect to connectivity, cohesion and the generalized cohesion criteria. It is then shown that this graph also has the smallest total number of distinct minimum size edge cut-sets and the smallest total number of distinct minimum size node cut-sets.Keywords
This publication has 3 references indexed in Scilit:
- On graphs of invulnerable communication netsIEEE Transactions on Circuit Theory, 1970
- A Graph-Theoretic Approach to a Communications ProblemSIAM Journal on Applied Mathematics, 1966
- THE MAXIMUM CONNECTIVITY OF A GRAPHProceedings of the National Academy of Sciences, 1962