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