PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 63 (77), pp. 31--36 (1998)
Distance of thorny graphs
Ivan GutmanPrirodno-matemati\v cki fakultet, Kragujevac, Yugoslavia
Abstract: Let $G$ be a connected graph on $n$ vertices. The thorn graph $G^\star$ of $G$ is obtained from $G$ by attaching to its $i$-th vertex $p_i$ new vertices of degree one, $p_i \geq 0$, $i=1,2,\ldots,n$. Let $d(G)$ be the sum of distances of all pairs of vertices of $G$. We establish relations between $d(G)$ and $d(G^\star)$\ and examine several special cases of this result. In particular, if $p_i=\gamma-\gamma_i$, where $\gamma$ is a constant and $\gamma_i$ the degree of the $i$-th vertex in $G$, and if $G$ is a tree, then there is a linear relation between $d(G^\star)$ and $d(G)$, namely $d(G^\star)=(\gamma-1)^2\,d(G)+[(\gamma-1)n+1]^2$.
Classification (MSC2000): 05C12
Full text of the article:
Electronic fulltext finalized on: 6 Apr 2000. This page was last modified: 16 Nov 2001.
© 2000 Mathematical Institute of the Serbian Academy of Science and Arts