Distance of Thorny Graphs
Publications de l'Institut Mathématique, _N_S_63 (1998) no. 77, p. 31
Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts
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$.
@article{PIM_1998_N_S_63_77_a4,
author = {Ivan Gutman},
title = {Distance of {Thorny} {Graphs}},
journal = {Publications de l'Institut Math\'ematique},
pages = {31 },
publisher = {mathdoc},
volume = {_N_S_63},
number = {77},
year = {1998},
zbl = {0942.05021},
language = {en},
url = {http://geodesic.mathdoc.fr/item/PIM_1998_N_S_63_77_a4/}
}
Ivan Gutman. Distance of Thorny Graphs. Publications de l'Institut Mathématique, _N_S_63 (1998) no. 77, p. 31 . http://geodesic.mathdoc.fr/item/PIM_1998_N_S_63_77_a4/