Journal of Combinatorics

Volume 8 (2017)

Number 2

The index problem of group connectivity

Pages: 305 – 321

DOI: http://dx.doi.org/10.4310/JOC.2017.v8.n2.a4

Authors

Miaomiao Han (Department of Mathematics, West Virginia University, Morgantown, W.V., U.S.A.)

Hong-Jian Lai (Department of Mathematics, West Virginia University, Morgantown, W.V., U.S.A.)

Yehong Shao (Arts and Science, Ohio University Southern, Ironton, Oh., U.S.A.)

Abstract

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 \{ m: \mbox{$G$ has a normal divalent path of length $m$.} \}\]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