مرکز منطقه ای اطلاع رساني علوم و فناوري

DocumentCode :

1184072

Title :

Optimum addition of an edge to a path

Author :

Cockayne, E.J. ; Miller, D.J.

Volume :

Issue :

fYear :

1980

fDate :

7/1/1980 12:00:00 AM

Firstpage :

649

Lastpage :

651

Abstract :

Let $Q(G)$ denote the sum taken over all vertex pairs $u,v$ of a graph $G$ of the shortest distance from $u$ to $v$ in $G$ . We determine the edges e which when added to the path $P_m$ minimize $Q(P_{m} + e)$ . For example, if $1,{\\cdots },2n+ 1$ is the vertex sequence of $P_{2n +1}$ , the unique optimum edge is $e=[a, 2n+2-a]$ , where $a = [n(\\sqrt {2} - 1)]$ .