The index problem of group connectivity. (English) Zbl 1367.05117

Han, Miaomiao; Lai, Hong-Jian; Shao, Yehong

J. Comb. 8, No. 2, 305-321 (2017).

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