z-logo
Premium
Tenacity of complete graph products and grids
Author(s) -
Choudum S. A.,
Priya N.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199910)34:3<192::aid-net3>3.0.co;2-r
Subject(s) - cartesian product , tenacity (mineralogy) , hypercube , computer science , graph , cartesian coordinate system , interconnection , conjecture , mathematics , combinatorics , discrete mathematics , theoretical computer science , telecommunications , materials science , geometry , composite material
Computer or communication networks are so designed that they do not easily get disrupted under external attack and, moreover, these are easily reconstructible if they do get disrupted. These desirable properties of networks can be measured by various parameters like connectivity, toughness, integrity, and tenacity. In an article by Cozzens et al., the authors defined the tenacity of a graph G ( V , E ) as min {| S | + τ( G − S )/ω( G − S ) : S ⊆ V }, where τ( G − S ) and ω( G − S ), respectively, denote the order of the largest component and number of components in G − S . This is a better parameter to measure the stability of a network G , as it takes into account both the quantity and order of components of the graph G − S . The Cartesian products of graphs like hypercubes, grids, and tori are widely used to design interconnection networks in multiprocessor computing systems. These considerations motivated us to study tenacity of Cartesian products of graphs. In this paper, we find the tenacity of Cartesian product of complete graphs (thus settling a conjecture stated in Cozzens et al.) and grids. © 1999 John Wiley & Sons, Inc. Networks 34: 192–196, 1999

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here