ACTA MATHEMATICA UNIVERSITATIS COMENIANAE
Vol. LXXII, 1(2003)
p. 59 – 66
Connectivity of Path Graphs
D. Ferrero
Abstract.
The aim of this paper is to lower bound the connectivity of $k$-path graphs. From the bounds obtained,
we give conditions to guarantee maximum connectivity. Then, it is shown that those maximally connected graphs
satisfying the previous conditions are also super-$\lambda$. While doing so, we derive some properties about
the girth and the diameter of path graphs. Finally, the results are extended to path graphs resulting from
the iteration of the $k$-path graph operator.
AMS subject classification:
05C75
Keywords:
Path graphs, connectivity, diameter, girth
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 2003, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE