On edge- addition problem | ||
| Journal of College of Education for Pure Science | ||
| Article 1, Volume 4, Issue 1, June 2014, Pages 26-36 | ||
| Authors | ||
| Alaa A. Najim; Suaad A. A. Suady | ||
| Abstract | ||
| For given positive integers and , "Edge-addition problem" can stated as: Given a graph with diameter and a positive integer ( < ) to obtain a graph from , how many edges must be added to such that the resulting has diameter of at most . Let denoted the minimum diameter of an altered graph obtained by adding extra edges to a graph with diameter . And let (res. cycle) denoted the minimum diameter of graph obtained by adding extra edges to a path (res. cycle) with diameter . Clearly that .Let denoted the minimum number of edges that have to be add to a path of length in order to obtain a graph of diameter at most . In this paper we find exact value to , for some and (res. and ). Also we prove if ( and ) or ( and ) | ||
| Keywords | ||
| Diameter; Altered graph; Edge addition | ||
|
Statistics Article View: 109 PDF Download: 84 |
||