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

© Copyright 2001, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE