ABSTRACT
Animportantconsiderationinthetopologicaldesignofanetworkisfaulttolerance,thatis,theabilityofthenetworktoprovideserviceevenwhenitcontains afaultycomponentorcomponents.Thebehaviorofanetworkinthepresence ofafaultcanbeanalyzedbydeterminingtheeffectthatremovinganedge(link failure)oravertex(processorfailure)fromitsunderlyinggraphGhasonthe fault-tolerancecriterion.Forexample,a-y-setinGrepresentsaminimumsetof processorsthatcancommunicatedirectlywithallotherprocessorsinthesystem.Ifitisessentialforfileserverstohavethispropertyandthatthenumber ofprocessorsdesignatedasfileserversbelimited,thenthedominationnumber ofGisthefault-tolerancecriterion.Inthisexample,itisimportantthat-y(G) doesnotincreasewhenGismodifiedbyremovingavertexoranedge.Fromanotherperspective,networkscanbemadefault-tolerantbyprovidingredundant communicationlinks(addingedges).Hence,weexaminetheeffectson-y(G) whenGismodifiedbydeletingavertexordeletingoraddinganedge.
