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)]$ .

Keywords

Communication networks; Circuits and systems; Communication networks; Cost function; Councils; Mathematics; Tree graphs;

fLanguage

English

Journal_Title

Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0098-4094

Type

jour

DOI

10.1109/TCS.1980.1084857

Filename

1084857

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1184072