DIAMETER IN PATH GRAPHS
Acta mathematica Universitatis Comenianae, Tome 68 (1999) no. 1
A. Belan; P. Jurica. DIAMETER IN PATH GRAPHS. Acta mathematica Universitatis Comenianae, Tome 68 (1999) no. 1. http://geodesic.mathdoc.fr/item/AMUC_1999_68_1_a9/
@article{AMUC_1999_68_1_a9,
     author = {A. Belan and P. Jurica},
     title = {DIAMETER {IN} {PATH} {GRAPHS}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1999},
     volume = {68},
     number = {1},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1999_68_1_a9/}
}
TY  - JOUR
AU  - A. Belan
AU  - P. Jurica
TI  - DIAMETER IN PATH GRAPHS
JO  - Acta mathematica Universitatis Comenianae
PY  - 1999
VL  - 68
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/AMUC_1999_68_1_a9/
ID  - AMUC_1999_68_1_a9
ER  - 
%0 Journal Article
%A A. Belan
%A P. Jurica
%T DIAMETER IN PATH GRAPHS
%J Acta mathematica Universitatis Comenianae
%D 1999
%V 68
%N 1
%U http://geodesic.mathdoc.fr/item/AMUC_1999_68_1_a9/
%F AMUC_1999_68_1_a9

Voir la notice de l'article provenant de la source Comenius University

If $G$ is a graph, then its path graph, $P_k(G)$, has vertex set identical with the set of paths of length $k$ in $G$, with two vertices adjacent in $P_k(G)$ if and only if the corresponding paths are ``consecutive'' in $G$. We construct bounds on the diameter of every component of $P_k(G)$ in form $diam(G)+f(k)$, where $f(k)$ is a function depending only on $k$. We have a general lower bound with $f(k)=-k$; upper bound for trees with $f(k)=k(k-2)$; and an upper bound for graphs with large diameter with $f(k)=k^2-2$, if $2\le k\le 4$. All bounds are best possible.