DIAMETER IN PATH GRAPHS
Acta mathematica Universitatis Comenianae, Tome 68 (1999) no. 1
Citer cet article
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.