ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 68, 1 (1999)
pp. 111-125

DIAMETER IN PATH GRAPHS
A. BELAN and P. JURICA

Abstract. 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.

AMS subject classification. 05C12, 05C38
Keywords. Diameter, path graph, line graph

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc