| As an essential tool for interconnected network research, the Theory of Combination Network is a new research field which comes from the crossing subjects of Mathematics and Computer Science. Edge-Adding Problem is one important part of the Combination Network, and is of great interest. However, it is quite hard to solve it, and Schoone et al have proved it a NPC problem.Given a connected graph H, we add t edges to it to form an Altered Graph G. The diameter of G varies as the different ways of adding edges to H, and finding the smallest diameter of these altered graphs is the so-called alternative form of Edge-Adding Problem. The research on this alternative form can contribute a lot to the solution of the Edge-Adding Problem.Let P(n,t) denote the least possible diameter for the altered graphs of an n-vertex path Pn, and let C(n,t) denote the corresponding value for the altered graphs of an n-vertex cycle Cn.Schoone et al proved that for all n > 5, P(n,2) =This paper focuses on the least diameter of the altered graphs formed by adding t(t = 3,4)edges to Cn. First, an instance of edge-adding method is provided to work out the upper bound of the C(n, t). Then, the lower bound of the C(n, t) is proved. As a result, the value of C(n, t)This paper also studies the altered graphs formed by addingt(t>4) edges to Pn, and improves the upper bound of P{n,l) by providing a special method of adding edges: let 0 = n mod 2(t+1), and when n > 5,... |
