Electronic Journal of Graph Theory and Applications

A bound on connectivity of iterated line graphs

Yehong Shao

Arts and Sciences Ohio University Southern Campus

Ironton, OH 45638

shaoy@ohio.edu

For simple connected graphs that are neither paths nor cycles, we define \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) that is not both of length 2 and in a \(K_3\)}, where a divalent path is a path whose internal vertices have degree two in G. Let G be a graph and \(L^n(G)\) be its n-th iterated line graph of G. We use \(\kappa'_e(G)\) and \(\kappa(G)\) for the essential edge connectivity and vertex connectivity of G, respectively. Let G be a simple connected graph that is not a path, a cycle or \(K_{1,3}\), with \(l(G) = l \ge 1\). We prove that (i) for integers \(s \ge 1\), \(\kappa'_e(L^{l+s}(G)) \ge 2^s + 2\); (ii) for integers \(s \ge 2\), \(\kappa(L^{l+s}(G)) \ge 2^{s-1} + 2\). The bounds are best possible.

Keywords: iterated line graphs, essential edge connectivity, vertex connectivity

Mathematics Subject Classification: 05C76

DOI: 10.5614/ejgta.2022.10.2.16

1. Introduction

We use [1] for terminology and notation not defined here, and consider finite and simple graphs only. Let A, B be two vertex sets in a graph G, and [A, B] denote the set of edges with one end in A and the other in B. In particular, \(\kappa(G)\) and \(\kappa'(G)\) represent the connectivity and edge-connectivity of a graph G, respectively. A graph is trivial if it contains no edges. An edge cut Y of G is essential if G - Y has at least two nontrivial components. For an integer k > 0, a graph G is essentially k-edge-connected if G does not have an essential edge cut Y with |Y| < k. We use \(\kappa'_e(G)\) to

Received: 27 June 2020, Revised: 17 July 2022, Accepted: 28 August 2022.

denote the essential edge connectivity of a graph G. A degree sum property follows immediately from the definition of essential edge connectivity.

Proposition 1.1. (Shao, Proposition 2.1 of [4]) Let \(n \ge 1\) be an integer and G be a graph which is not \(K_{1,n-1}\) or \(K_3\). Then the degree sum of any two adjacent vertices is at least \(\kappa'_e(G) + 2\).

The line graph of a graph G, denoted by L(G) or \(L^1(G)\), has E(G) as its vertex set, where two vertices in L(G) are adjacent if and only if the corresponding two edges in G have a common vertex. Iteratively, \(L^n(G) = L(L^{n-1}(G))\) and \(L^0(G) = G\) for integers \(n \geq 1\). The following connectivity properties can be derived from the definitions.

Proposition 1.2. (Shao, Proposition 1.2 of [4]) Let \(n \ge 1\) be an integer and G be a graph which is not \(K_3\) or \(K_{1,n-1}\). Then each of the following holds.

• (i) \(\kappa'_e(G) \ge \kappa'(G)\).
• (ii) \(\kappa'_e(G) = \kappa(L(G))\).
• (iii) \(\kappa'_e(L(G)) \ge \kappa'_e(G)\).
• (iv) \(\kappa(L(G)) \ge \kappa(G)\).

Proposition 1.2(ii) indicates that it is useful to investigate properties of essential edge connectivity in order to obtain properties of vertex connectivity in line graphs. Here is a result on how essential edge connectivity grows for iterated line graphs.

Theorem 1.1. (Shao, Theorem 1.3 of [4]) Let \(n \ge 1\) be an integer and G be a graph which is not \(K_{1,n-1}\) or \(K_3\). If G does not contain degree two vertices, then \(\kappa'_e(L(G)) \ge 2\kappa'_e(G) - 2\).

For simple connected graphs that are neither paths nor cycles, we define \(l(G) = \max\{m : G \text{ has a divalent path of length } m \text{ that is not both of length } 2 \text{ and in a } K_3\}\), where a divalent path is a path whose internal vertices have degree two in G. We call l(G) the divalent length of G.

For the graph G depicted in Figure 1, \(\kappa'_e(L(G)) = \kappa'_e(G) = 3\); the one in Figure 1, \(\kappa'_e(L(G)) = \kappa'_e(G) = 1\). In many cases as these graphs depicted in Figures 0 and 1, when G has a divalent path with internal vertices of degree two, the connectivity of the line graphs stays the same. Since each iteration will reduce the lengths of all divalent paths by one, after l(G) - 1 times of iterations, the internal vertices of degree 2 either disappear or lie in a triangle, and the connectivity is likely to increase.

Figure 1. An example for \(\kappa'_e(L(G)) = \kappa'_e(G)\).

A former result gives a bound on the essential edge connectivity of the (l+1)-th iterated line graphs.

Proposition 1.3. (Zhang et al., Lemma 2.5 of [6]) Let G be a connected graph with l(G) = l. Then κ ′ e (L ^l+1(G)) ≥ 4.

In this note, we obtain the bounds for essential edge connectivity and connectivity of iterated line graphs.

Theorem 1.2. Let G be a simple connected graph that is not a path, a cycle or K1,3, with l(G) = l ≥ 1. Then each of the following holds:

• (i) For integers s ≥ 1, κ ′ e (L l+s (G)) ≥ 2 ^s + 2. The bound is best possible.
• (ii) For integers s ≥ 2, κ(L l+s (G)) ≥ 2 ^s−¹ + 2. The bound is best possible.

Note that (i) does not hold for s = 0 and (ii) does not hold for s = 1 as there exist graphs with κ ′ e (L l (G)) = κ(L ^l+1(G)) = 2. As shown in Figure 2(a), l(G) = 2 and in Figure 2(c), κ ′ e (L 2 (G)) = 2. By Proposition 1.2(ii), κ(L 3 (G)) = κ ′ e (L 2 (G)) = 2.

Figure 2. An example to show (i) does not hold for s = 0.

2. Previous Results

For a graph G and a vertex v ∈ V (G), define

\[N_G(v) = \{u \in V(G) : u \text{ is adjacent to } v \text{ in } G\}\]

and

\[E_G(v) = \{e \in E(G) : e \text{ is incident with } v \text{ in } G\}.\]

Let L(G) be the line graph of G, and

\[X\] be a minimal essential edge cut of \(L(G)\). (1)

By (1), L(G) − X has exactly two nontrivial components, so we assume

\[L_1, L_2\] are the only two nontrivial components of \(L(G) - X\). (2)

By (2), V (L(G)) is a disjoint union of V (L1) and V (L2). By the definition of line graphs, E(G) is a disjoint union of two edge sets corresponding to V (L1) and V (L2). For each edge e ∈ E(G), let v^e ∈ V (L(G)) denote its corresponding vertex in the line graph L(G). Let f : E(G) 7→ {1, 2} be a 2-edge-coloring of G such that

\[f(e) = i\] if and only if \(v_e \in V(L_i)\) for \(i = 1, 2\).

Proposition 2.1. (Shao, [3]) Let G be a graph, e1, e² ∈ E(G) and v^e1 , v^e2 ∈ V (L(G)) be their corresponding vertices in the line graph L(G). Then each of the following holds:

• (i) For i = 1, 2, |{e ∈ E(G) : f(e) = i}| = |V (Li)| ≥ 2.
• (ii) v^e1 v^e2 ∈ X if and only if e1, e² share a common vertex and f(e1) ̸= f(e2).

A vertex of a graph G is mono-colored if all incident edges have the same color in G, and a vertex is bi-colored if the incident edges have two different colors.

Proposition 2.2. (Shao, [3]) Let G be a graph, V¹² the set of all bi-colored vertices of G, or equivalently,

\[V_{12} = \{ v \in V(G) : \text{ there exist } e_1, e_2 \in E_G(v) \text{ such that } f(e_1) = 1 \text{ and } f(e_2) = 2 \}.\] (3)

Then each of the following holds.

• (i) dG(v) ≥ 2 for each v ∈ V12.
• (ii) Each vertex of G − V¹² is mono-colored in G, and moreover, for each component H of G − V12, all edges with at least one end in H have the same color as the edges of H.
• (iii) If 1 ≤ |V12| ≤ 3 and V¹² is not a vertex cut, then the subgraph of G induced by V12, G[V12], is connected.
  • (iv) If |V12| = 1 or 2, then V¹² is a vertex cut of G.

Let u ∈ V (G) and

\[E_i(u) = \{e \in E_G(u) : f(e) = i\} \text{ for } i = 1, 2.\] (4)

Proposition 2.3. (Shao, Proposition 2.4 of [4]) Each of the following holds:

• (i) |X| = P u∈V¹² |E1(u)| · |E2(u)|.
• (ii) For each u ∈ V¹² and i = 1, 2, |E1(u)| · |E2(u)| ≥ dG(u) − 1.
• (iii) If for each u ∈ V¹² and i = 1, 2, |Ei(u)| ≥ 2, then |E1(u)| · |E2(u)| ≥ 2(dG(u) − 2).

A graph G is k-triangular if each edge of G lies in at least k triangles and G is triangular if it is 1-triangular. We summarize some properties of iterated line graphs of G in terms of l(G) as follows.

Proposition 2.4. (Zhang, Eschen, Lai and Shao, Lemma 3.2 of [5]) Let G be a simple connected graph that is not a path, a cycle or K1,3, with l(G) = l ≥ 1. Then each of the following holds: (i) For an integer m ≥ 0,

\[l(L^m(G)) = \begin{cases} l - m, & \text{if } 0 \le m < l, \\ 1, & \text{if } m \ge l. \end{cases}\]

(ii) For integers k ≥ 0,

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

• (iii) L l (G), L ^l+1(G) and L ^l+2(G) are triangular. Moreover, L l+k (G) is 2 k−3 -triangular when k ≥ 3.
• (iv) For an integer k ≥ 0, κ(L l+k (G)) ≥ k + 1.

3. Proof of Theorem 1.2

In this section, we first prove Proposition 3.1, then apply induction on s to prove Theorem 1.2. Following the definitions of X, \(V_{12}\) and \(E_i(u)\) (see (1), (3) and (4)) in Section 2, let X be a minimal essential edge cut of \(L^{l+2}(G)\) and \(V_{12}\) the set of bi-colored vertices in \(L^{l+1}(G)\). And \(E_i(u)\) denotes the set of edges incident with u in \(L^{l+1}(G)\) with color i. We use d(v) for \(d_{L^{l+1}(G)}(v)\). Now we prove Theorem 1.2(i) holds for s=2.

Proposition 3.1. Let G be a simple connected graph that is not a path, a cycle or \(K_{1,3}\), with l(G) = l. Then \(\kappa'_e(L^{l+2}(G)) \geq 6\).

Proof. If \(\delta(L^{l+1}(G)) \geq 3\), then by Theorem 1.1 and Proposition 1.3, \(\kappa'_e(L^{l+2}(G)) \geq 2\kappa'_e(L^{l+1}(G)) - 2 = 2 \cdot 4 - 2 = 6\). Then Proposition 3.1 is proved.

Also, by Proposition 2.4(ii),

\[\delta(L^{l+1}(G)) \ge 2. \tag{5}\]

Y. Shao

So we may assume that \(\delta(L^{l+1}(G)) = 2\).

By Proposition 2.4(iv), \(\kappa(L^{l+1}(G)) \geq 2\). By Proposition 2.2(iv), if \(|V_{12}| = 1\), then \(V_{12}\) is a vertex cut of size one in \(L^{l+1}(G)\), a contradiction. So \(|V_{12}| \geq 2\).

Claim 1. If \(|V_{12}| = 2\), then \(|X| \ge 6\).

Proof of Claim 1. Let \(V_{12} = \{v_1, v_2\}\). If \(v_1v_2 \notin E(L^{l+1}(G))\), then as \(L^{l+1}(G)\) is triangular (Proposition 2.4(iii)), and \(v_i\) is bi-colored, \(|E_i(v_1)| \ge 2\) for i = 1, 2 by Proposition 2.2(ii). By Proposition 2.3(i) and (iii), \(|X| \ge \sum_{i=1}^{|V_{12}|} 2(d(v_i) - 2) \ge 2 \cdot 2 + 2 \cdot 2 = 8\).

So we may assume \(v_1v_2 \in E(L^{l+1}(G))\). By Proposition 2.2(iv), \(V_{12}\) is a vertex cut of \(L^{l+1}(G)\). So we will finish the proof of Claim 1 by the following three cases.

Case 1 of Claim 1. \(L^{l+1}(G) - V_{12}\) has at least two nontrivial components.

Proof of Case 1. Let \(G_1, G_2\) be two nontrivial components of \(L^{l+1}(G) - V_{12}\). By Proposition 1.3, \(\kappa'_e(L^{l+1}(G)) \ge 4\). Then \(|[V(G_i), V_{12}]| \ge 4\) for i = 1, 2, which implies \(d(v_1) + d(v_2) \ge 4 + 4 + 2 = 10\). By Proposition 2.3(i) and (ii), \(|X| \ge (d(v_1) - 1) + (d(v_2) - 1) = d(v_1) + d(v_2) - 2 \ge 10 - 2 = 8\). □

Case 2 of Claim 1. \(L^{l+1}(G) - V_{12}\) has at most one nontrivial component.

Proof of Case 2. Let \(G_1\) be the nontrivial component and \(G_2\) be a single vertex component (say u) of \(L^{l+1}(G)-V_{12}\). Since \(\kappa'_e(L^{l+1}(G))\geq 4\) (Proposition 1.3), \(|[V(G_1),V_{12}]|\geq 4\). Since u is a single vertex component of \(L^{l+1}(G)-V_{12}\), by (5), we have \(uv_1\in E(L^{l+1}(G))\) and \(uv_2\in E(L^{l+1}(G))\). So \(d(v_1)+d(v_2)\geq 4+2+2=8\). By Proposition 2.3(i) and (ii), \(|X|\geq (d(v_1)-1)+(d(v_2)-1)=d(v_1)+d(v_2)-2\geq 8-2=6\).

Case 3 of Claim 1. Every component of \(L^{l+1}(G) - V_{12}\) is trivial.

Then \(L^{l+1}(G)\) is isomorphic to \(K_{2,n-2}\) with an edge joining the two vertices of degree two, where n is the number of vertices of \(L^{l+1}(G)\). If n=4, then it has an essential 3-edge-cut, contrary to Proposition 1.3; if \(n\geq 4\), then it contains an induced claw, contrary to the fact that line graphs are claw-free (see [2]).

Claim 2. If \(|V_{12}| \ge 6\), then \(|X| \ge 6\).

Proof of Claim 2. If \(|V_{12}| \ge 6\), then by (5) and Proposition 2.3(i) and (ii), \(|X| \ge \sum_{i=1}^{|V_{12}|} (d(v_i) - 1) \ge (2 - 1)|V_{12}| = 6\). □

By Claims 1 and 2, we may assume that

\[3 \le |V_{12}| \le 5. \tag{6}\]

Claim 3. If the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) contains at least two independent edges, then \(|X| \geq 8\).

Proof of Claim 3. We assume that \(v_1, v_2, v_3, v_4 \in V_{12}\) such that \(v_1v_2 \in E(L^{l+1}(G))\) and \(v_3v_4 \in E(L^{l+1}(G))\). By Proposition 1.1, \(d(v_1)+d(v_2) \geq \kappa'_e(L^{l+1}(G))+2\) and \(d(v_3)+d(v_4) \geq \kappa'_e(L^{l+1}(G))+2\). By Proposition 2.3(i), (ii) and Proposition 1.3, \(|X| \geq \sum_{i=1}^4 (d(v_i)-1) = \sum_{i=1}^4 d(v_i)-4 \geq 2(\kappa'_e(L^{l+1}(G))+2)-4=2\cdot(4+2)-4=8\). This completes the proof of Claim 3. □

By Claim 3, we may assume that

the matching number of the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is at most one. (7)

Claim 4. If the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) has an isolated vertex, then \(|X| \ge 6\).

Proof of Claim 4. Without loss of generality, we assume \(v_1\) is an isolated vertex in the induced graph of \(V_{12}\) in \(L^{l+1}(G)\). Since \(L^{l+1}(G)\) is triangular (Proposition 2.4(iii)), and \(v_1\) is bi-colored, \(|E_i(v_1)| \geq 2\) for i=1,2 by Proposition 2.2(ii). By (6), \(|V_{12}| \geq 3\). Together with Proposition 2.3(i), (ii), (iii) and (5), we have \(|X| = \sum_{u \in V_{12}} |E_1(u)| \cdot |E_2(u)| \geq 2(d(v_1)-2)+(2-1)\cdot (|V_{12}|-1) \geq 2\cdot 2+(3-1)=6\).

By Claim 4, we may assume

the induced graph of \[V_{12}\] in \(L^{l+1}(G)\) has no isolated vertices. (8)

Claim 5. The induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is isomorphic to \(K_3\) or \(K_{1,2}\).

Proof of Claim 5. By (7) and (8), the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is isomorphic to \(K_3\) or \(K_{1,|V_{12}|-1}\). If \(4 \leq |V_{12}| \leq 5\), then \(K_{1,|V_{12}|-1}\) contains a claw, contrary to the fact that \(L^{l+1}(G)\) is claw-free. So by (6), \(|V_{12}| = 3\) and by (7) and (8), the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is isomorphic to \(K_3\) or \(K_{1,2}\).

Claim 6. If each vertex in the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) has degree at least three, then \(|X| \geq 6\).

Proof of Claim 6. Let \(V_{12} = \{v_1, v_2, v_3\}\) and assume \(d(v_i) \geq 3\) for i = 1, 2, 3. By Proposition 2.3(i), (ii) and (6), \(|X| \geq \sum_{i=1}^{3} (d(v_i) - 1) \geq (3-1)|V_{12}| \geq 6\).

By Claim 6, we assume

at least one vertex in the induced graph of \[V_{12}\] in \(L^{l+1}(G)\) has degree two. (9)

Now we will finish the proof of Theorem 1.2 by the following two cases.

Case 1. \(L^{l+1}(G) - V_{12}\) is connected.

Proof of Case 1. Let G' be the graph induced by \(L^{l+1}(G) - V_{12}\). By Proposition 2.2(ii), we assume all edges in \([V(G'), V_{12}]\) have color 1. As \(v_1, v_2, v_3\) are bi-colored, if the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is \(K_{1,2}\), then both edges of \(K_{1,2}\) must have color 2; if the induced graph of \(V_{12}\) in \(L^{l+1}(G)\) is \(K_3\), then by Proposition 2.1(i), at least two edges of \(K_3\) have color 2. In

either case, without loss of generality we may assume that both v1v² and v2v³ have color 2, which means |E2(v2)| ≥ 2. Since v² is bi-colored, there is an edge in [V (G′ ), {v2}] with color 1, which implies that the degree of v² is at least three. By (9), we may assume d(v1) = 2, then d(v2) ≥ 4 by Propositions 1.1 and 1.3. Then |[V (G′ ), {v2}]| ≥ 2 and so |E1(v2)| ≥ 2. Together with |E2(v2)| ≥ 2, by Proposition 2.3(i), (ii) and (iii), |X| ≥ 2(d(v2)−2) + (d(v1)−1) + (d(v3)−1) ≥ 2 · 2 + (2 − 1) + (2 − 1) = 6.

Case 2. L ^l+1(G) − V¹² is disconnected.

By Claim 5, we only need to prove Case 2 by the following two cases.

Case 2.1. The induced graph of V¹² in L ^l+1(G) is isomorphic to K3.

Proof of Case 2.1. By (9), without loss of generality, we assume that d(v2) = 2, then by Propositions 1.1 and 1.3, d(v1) ≥ 4 and d(v3) ≥ 4. By Proposition 2.3(i) and (ii), |X| ≥ (d(v1) − 1) + (d(v2) − 1) + (d(v3) − 1) ≥ (4 − 1) + (2 − 1) + (4 − 1) = 7.

Case 2.2. The induced graph of V¹² in L ^l+1(G) is isomorphic to K1,2.

Proof of Case 2.2. Assume v1v² ∈ E(L ^l+1(G)) and v2v³ ∈ E(L ^l+1(G)). If d(v2) = 2, then by Propositions 1.1 and 1.3, d(v1) ≥ 4 and d(v3) ≥ 4. Using a similar argument to Case 2.1, we have |X| ≥ 7.

By (9), we may assume that d(v1) = 2.

Then by Propositions 1.1 and 1.3 again, d(v2) ≥ 4. If d(v3) ≥ 3, then |X| ≥ (d(v1) − 1) + (d(v2) − 1) + (d(v3) − 1) ≥ (2 − 1) + (4 − 1) + (3 − 1) = 6. So we assume d(v3) = 2.

If d(v2) ≥ 5, then |X| ≥ (d(v1)−1)+(d(v2)−1)+(d(v3)−1) ≥ (2−1)+(5−1)+(2−1) = 6. So we assume d(v2) = 4.

Now we have d(v1) = d(v3) = 2 and d(v2) = 4. Since L ^l+1(G) is triangular, we assume v1v2, v2v³ lie in triangles T1, T2, respectively. If T1, T² share a common edge, then L ^l+1(G) must be the graph depicted in Figure 3(a), where H represents a connected subgraph containing the edge u1u2; if T1, T² do not share a common edge, then L ^l+1(G) must be the graphs depicted in Figure 3(b) and 3(c), where H in 2(b) represents a connected subgraph containing the vertices u1, u² and two circles in 2(c) represent either two isolated vertices u1, u² or two disjoint connected subgraphs containing u1, u2, respectively. In Figure 3(a) and 3(b), since H is a connected subgraph, L ^l+1(G) − V¹² is connected, contrary to the assumption of Case 2; in Figure 3(c), L ^l+1(G) has an essential 2-edge-cut, contrary to Proposition 1.3.

Figure 3. Iterated Line graph L ^l+1(G).

This completes Case 2.2.

Hence, Proposition 3.1 is established.

Next we will use Proposition 3.1 to prove Theorem 1.2.

Proof of Theorem 1.2(i). The case s=1 is implied by Proposition 1.3 and the case s=2 is implied by Proposition 3.1. We assume \(s\geq 3\).

By Proposition 2.4(ii), for \(s\geq 3\), \(\delta(L^{l+s-1}(G))\geq 3\). Now we prove (i) by induction. Assume that \(\kappa'_e(L^{l+s-1}(G))\geq 2^{s-1}+2\). By Theorem 1.1, \(\kappa'_e(L^{l+s}(G))\geq 2\kappa'_e(L^{l+s-1}(G))-2\geq 2(2^{s-1}+2)-2=2^s+2\). Then (i) is proved. \(\square\) Proof of Theorem 1.2(ii). By (i) and Proposition 1.2(ii), for \(s\geq 2\), \(\kappa(L^{l+s}(G))=\kappa'_e(L^{l+s-1}(G))\geq 2^{s-1}+2\). \(\square\)

Next we give an example to show that both bounds in Theorem 1.2 are best possible. Let G be the graph depicted in Figure 4(a). Then l(G)=2. The first three iterated line graphs of G are depicted in Figure 4(b)-(d). Note that \(L^3(G)\) has a 4-cycle in which every vertex has degree equal to 3. By the definition of line graphs, a 4-cycle of a graph generates a 4-cycle in its line graph, and the degree of a vertex in a line graph is the degree sum of the end vertices of the corresponding edge in the original graph minus 2. So \(L^4(G)\) has a 4-cycle in which every vertex has degree equal to \(2 \cdot 3 - 2 = 4\). In general, for \(s \geq 2\), \(L^{l+s}(G)\) has a 4-cycle in which every vertex has degree equal to \(2^{s-1}+2\). Let \(uv \in E(L^{l+s}(G))\) be an edge on the 4-cycle such that both u and v have degree equal to \(2^{s-1}+2\). Then \(E_{L^{l+s}(G)}(u) \cup E_{L^{l+s}(G)}(v) - \{uv\}\) is an essential edge cut of size \(2 \cdot (2^{s-1}+2) - 2 = 2^s + 2\). Note that \(\kappa'_e(L^{l+1}(G)) = \kappa'_e(L^3(G)) = 4\). Hence \(\kappa'_e(L^{l+s}(G)) = 2^s + 2\) for \(s \geq 1\). By Proposition 1.2(ii), \(\kappa(L^{l+s}(G)) = \kappa'_e(L^{l+s-1}(G)) = 2^{s-1} + 2\) for \(s \geq 2\).

Figure 4. An example for the sharpness of the bounds.

References

• [1] J.A. Bondy and U.S.R. Murty, Graph theory with applications, Macmillan, London and Elsevier, New York, 1976.
• [2] R.L. Hemminger and L.W. Beineke, Line Graphs and Line Digraphs, in L.W. Beineke and R.J. Wilson, ed., Selected Topics in Graph Theory, Academic Press, New York, 1978, pp. 271-305.
• [3] Y. Shao, Connectivity of iterated line graphs, Discrete Applied Mathematics 158 (2010), 2081-2087.
• [4] Y. Shao, Essential edge connectivity of line graphs, Discrete Math. 341 (2018), 3441-3446.

• [5] L. Zhang, E. Eschen, H.J. Lai, and Y. Shao, The s-hamiltonian index, Discrete Math. 308 (2008), 4779-4785.
• [6] L. Zhang, Y. Shao, G. Chen, X. Xu, and J. Zhou, s-vertex pancyclic index,Graphs and Combinatorics 28 (2012), 393-406.