Diametes Of Altered Graphs With Related Problems

If the line fails, information transfer delay will occur, during the information transmitting in the network. A natural question is how at least many edges have to be added to the network to ensure the transmission delay within the effective bounds. In graph theory, this is the edge addition question. Let F(t, d) demote the minimum diameter of an altered graph obtained from a graph of diameter d by adding t extra edges. The purpose is trying to get the minimum of the F(t, d).Many people have studied this question and made a lot of profound conclu-sions, since F.R.K.Chung and M.R.Garey starting researching this problem in1984. This thesis attempts to survey some results on this topic and gives new proofs of some results.The first chapter introduces the basics of graph theory. The second chapter proves adding edge to a graph is equivalent to a path. After introducing the progress made so far, the bounds of F(t, d) is obtained by a new method. Finally, this paper describes the question of edges addition in a cycle.