The index problem of group connectivity

Let $G$ be a connected graph and $L(G)$ be its line graph. Define $L^0(G) = G$ and for any integer $k \ge 0$, the kth iterated line graph of $G$, denoted by $L^k(G)$, is defined recursively as $L^{k + 1}(G) = L(L^k(G))$. For a graphical property $\mathcal{P}$, the $\mathcal{P}$ - index of $G$ is the smallest integer $k \ge 0$ such that $L^k(G)$ has property $\mathcal{P}$. In this paper, we investigate the indices of group connectivity, and determine some best possible upper bounds for these indices. Let $A$ be an abelian group and let $i_A(G)$ be the smallest positive integer $m$ such that $L^m(G)$ is $A$-connected. A path $P$ of $G$ is a normal divalent path if all internal vertices of $P$ are of degree $2$ in $G$ and if $\lvert E(P) \rvert = 2$, then $P$ is not in a 3-cycle of $G$. Let\[l(G) = \max \lbrace m : G \: \text{has a normal divalent path of length} \: m \text{.}\rbrace\]In particular, we prove the following:

(i) If $ \lvert A \rvert \ge 4$, then $i_A(G) \leq l(G)$. This bound is best possible.

(ii) If $ \lvert A \rvert \ge 4$, then $i_A(G)\leq \lvert V(G) \rvert - \Delta(G)$. This bound is best possible.

(iii) Suppose that $ \lvert A \rvert \ge4$ and $d = \mathit{diam}(G)$. If $d \leq \lvert A \rvert - 1$, then $i_A(G) \leq d$; and if $d \ge \lvert A \rvert $, then $i_A(G) \leq 2d - \lvert A \rvert + 1$.

(iv) $i_{\mathbb{Z}_3}(G) \leq l(G) + 2$. This bound is best possible.

Full Text (PDF format)

Published 14 February 2017