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

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