A Study Of Several Classes Of Minimally And Maximally T-tough Graph

In this information age,Internet is indispensable to people's activities such that study,life,work,etc.Because network interruption often causes significant losses,the research of network invulnerability has important theoretical significance and practical value.Usually,a network can be modeled by a connected graph.The basic research method of invulnerability is to describe the"minimum"cost and the state of the remained network after a network has been destroyed.Toughness is considered to be a well invulnerability parameter.The construction of extreme graphs in the sense of toughness is an important subject.This thesis mainly studies the problems related to the minimally and maximally t-tough graphs.Firstly,based on the definition and relevant conclusions of the minimally t-toughness,the maximally t-toughness of several special graphs is analyzed,and two types of minimally t-tough graphs are constructed.Secondly,the concept of maximally t-tough is proposed,and the property of maximally t-tough of star graphs and windmill graphs are proved.Based on cycles and stars,two classes of 1-tough and (?)-tough graph are constructed.By the design of integer programming models and the optimization method,the minimum and maximum size of the two maximally t-tough graphs are given.The maximally and minimally t-tough graphs are the optimization of network invulnerability in the sense of toughness,and they have important value for network design.The construction methods and conclusions of the extreme graphs given in this thesis have certain reference significance for the study of network invulnerability.