On The Edge Addition And Deletion Of Graphs

The underlying topology of an interconnection network of a system is modelled by a graph G, the diameter of G is an important measure for communication efficiency and delay of the system. In a real-time system, the delay must be limited within a given period since any message obtained beyond the bound may be worthless. If the message delay exceeds a given time-bound in a network, one often adds some links to the network to ensure the reach of a message can be within a required time.It has been proved that the minimum diameter of an altered graph obtained from a graph with diameter d by adding t extra edges is equal to the minimum diameter of an altered graph obtained from a path with diameter d by adding t extra edges.This thesis attempts to study "the edge- addition problem" and "the edge-deletion problem": Determine the minimum diameter P(t,d) (resp. C(t,d)) of a connected graph obtained from a single path (resp. cycle) of diameter d plus t extra edges; the minimum number Tp(p, d) (resp. Tc(p, d)) of edges that have to be added to a path (resp. cycle) of length d to transform it to a graph of diameter at most p; and the maximum diameter f(t, d) of a connected graph obtained after deleting t edges from a connected graph of diameter d.In Chapter two, we prove P(t, d) ≤ 2k or 2k + 1 when t or d satisfies some conditions on an integer k. These upper bounds are used in our the proofs of our main results.In chapter three, we obtain the main results in this thesis as follows.