On edge-addition problem

Abstract EN

For given positive integerst and d, "Edge-addition problem" can stated as : Given a graph G with diameter d and a positive integer d ' (d '< d ) to obtain a graph H from G, how many edges must be added to G such that the resulting H has diameter of at most d '.

Let F (t, d) denoted the minimum diameter of an altered graph obtained by adding t  extra edges to a graph with diameter d.

And let p (t, d) (res.

cycle) denoted the minimum diameter of graph obtained by adding t  extra edges to a path (res.

cycle) with diameter d.

Clearly that F (t, d)  p(t, d).

Let ( , ) p T P d denoted the minimum number of edges that have to be add to a path of length d in order to obtain a graph of diameter at most P.

In this paper we find exact value to p (t, d) , ( , ) p T P d for some t and d (res.

P and d).

Also we prove C (t, d) C (t, d ') if (d  d ' and t t ') or (d  d 'and t t ').