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.
05C40 Connectivity
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI