# zbMATH — the first resource for mathematics

The index problem of group connectivity. (English) Zbl 1367.05117
Summary: Let $$G$$ be a connected graph and $$L(G)$$ be its line graph. Define $$L^0(G)=G$$ and for any integer $$k\geq 0$$, the $$k$$th 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 $$P$$, the $$P$$-index of $$G$$ is the smallest integer $$k\geq 0$$ such that $$L^k(G)$$ has property $$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 $$|E(P)|=2$$, then $$P$$ is not in a 3-cycle of $$G$$. Let $l(G)=\max\{m:\;G \text{ has a normal divalent path of length } m\}.$
In particular, we prove the following:
(i) If $$|A|\geq 4$$, then $$i_A(G)\leq l(G)$$. This bound is best possible.
(ii) If $$|A|\geq 4$$, then $$i_A(G)\leq |V(G)|-\Delta(G)$$. This bound is best possible.
(iii) Suppose that $$|A|\geq 4$$ and $$d=\text{diam}(G)$$. If $$d\leq |A|-1$$, then $$i_A(G)\leq d$$; and if $$d\geq |A|$$, then $$i_A(G)\leq 2d-|A|+1$$
(iv) $$i_Z3(G)\leq l(G)+2$$. This bound is best possible.
##### MSC:
 05C40 Connectivity 05C76 Graph operations (line graphs, products, etc.)
##### Keywords:
line graph; Hamiltonian index
Full Text: