Khalid Kamyab^a , Mohsen Ghasemi^a , Rezvan Varmazyar^b

kh.kamyab@urmia.ac.ir, m.ghasemi@urmia.ac.ir, varmazyar@iau.ac.ir

Suppose that G is minimally 4-restricted edge connected graph without triangle, δ(G) ≥ 2 and α4(G) ≥ 6. Suppose that A is a λ4-atom of G such that for each path of length 3 in A, say P³ = xyz, we have dA(y) − 1 = dA−{x,y,z}(y), where x ∼ y ∼ z. In this paper, under these assumptions, we show that all atoms of G are trivial.

Keywords: λ4-optimal, restricted edge connectivity, atom Mathematics Subject Classification : 05C40, 05C82

DOI: 10.5614/ejgta.2025.13.2.10

1. Introduction

Let G be a finite simple graph with vertex set V (G) and edge set E(G). For each vertex v ∈ V (G), the neighborhood N(v) of v is defined as the set of all vertices adjacent to v and d(v) = |N(v)| is the degree of v. For two vertices u, v ∈ V (G), we write u ∼ v (or uv ∈ E(G)) when u and v are adjacent. For two disjoint vertex set U1, U² ⊆ V (G), denote by [U1, U2]^G the set of edge of G with one end in U¹ an the other end in U2, G[U] is the subgraph of G induced by vertex set U ⊂ V (G), U = V (G) − U is the complement of U, wG(U) = |[U, U]G| is the number of edges between U and U. When the graph under consideration is obvious, we omit the subscript G. For a subset S ⊆ G write dS(U) = |[U, S − U]| and dS(u) = dS{u}.

A m-restricted edge cut is an edge cut of a connected graph that separates this graph into components each having order at least m vertices. The size of a minimum m-restricted edge cut of graph G is called its restricted edge connectivity and denoted by λm(G). A m-restricted edge cut S with |S| = λm(G) is called a λm-cut. Let εm(G) = min{|w(U)|, |U| = m and G[U] is connected}.

Received: 5 January 2020, Revised: 13 September 2025, Accepted: 29 September 2025.

^a Department of Mathematics, Urmia University, Urmia 57135, Iran

^bDepartment of Mathematics, Khoy.C., Islamic Azad University, Khoy 58168-44799, Iran

A graph G is λm-graph (or λm-optimal) if λm(G) = εm(G). There is much research on sufficient conditions for a graph to be λm-optimal, such as symmetric conditions [12, 14, 16, 17] degree conditions [14, 15, 18]. For more information on this topic we refer the reader to the [5].

A graph G is λ4-independent if each component of G has at most three vertices. A connected graph of order at most three is λ4-trivial. A graph is called λ4-non-trivial if it has a component which contains at least four vertices.

For two disjoint non-empty subsets X and Y of V (G), the following inequality is well known (see Lovasz 1979, Problem 6.48). ´

\[w(X \cap Y) + w(X \cup Y) \le w(X) + w(Y). \tag{1}\]

A vertex set U is called a λm-fragment if [U, U] is a minimum m-restricted edge cut of graph G. λm-restricted edge fragment with the least cardinality is called a λm-atom. The cardinality of λmatom is denoted by αm(G). Clearly m ≤ αm(G) ≤ |V (G)|/2. An atom is said to be trivial if it is a single cycle. In this paper we give another type of sufficient condition called a minimally restricted edge connected condition. A graph G is a minimally m-restricted edge connected (minimally λmgraph for short) if λm(G − e) < λm(G) for each e ∈ E(G). If e is a pending edge then G − e doesnot have λm-cut for m ≥ 2. So we always assume δ(G) ≥ 2 where G is a minimally λmgraph for some m ≥ 2 and δ(G) is the minimum degree of G. A minimally λ1-graph is exactly a minimally edge connected graph, which has been shown to be λ-optimal ( [10, Exercise 49]). In [6] the authors have proved that every minimally λ2-graph is λ2-optimal. Also in [7] the authors have proved that every minimally λ3-graph is always λ3-optimal except the 3-cube. For more information on this topic we refer the reader to the [1, 2, 3, 4, 8, 9, 11, 13]. In this paper with the similar methods we show that all atoms of a minimally 4-restricted edge connected graph without triangle are trivial (see Figure 1).

2. Main result

Throughout in this section we assume that G is a λ4-connected graph, δ(G) ≥ 2 and α4(G) ≥ 6. First with the similar arguments in the proofs of Lemmas 1 − 5 in [7] we have the following five results.

Lemma 2.1. Suppose that F is a subset of G such that G[F] is connected. If one of the following conditions is satisfied:

(i) \[w(F) < \lambda_4(G)\], or
(ii) \(w(F) = \lambda_4(G)\) and \(|F| < \alpha_4(G)\),
then \(G[F]\) is \(\lambda_4\)-independent.

Proof. Suppose that C is λ4-non-trivial component of G[F]. Since G[C] is connected, we have w(F) ≥ w(C) ≥ λ4(G) which contradicts the first condition. Also if condition (ii) occurs then we have w(F) = w(C) = λ4(G). Hence V (C) is a λ4(G)-fragment. But we have |F| ≥ |C| ≥ α4(G) which contradicts the second condition. Thus G[F] is λ4-independent, as wanted.

Lemma 2.2. Suppose that A is a λ4-atom of G and B is a λ4-fragment of G. (i) If U is a subset of A such that G[U] is connected and G[A\U] has λ4-non-trivial component,

then dA(U) > dA(U).

(ii) If U is a subset of B such that G[U] is connected and G[B\U] has λ4-non-trivial component, then dB(U) ≥ dB(U).

(iii) δ(G[A]) ≥ 2.

• Proof. (i) Suppose to contrary that dA(U) ≤ dA(U). Now we have w(A − U) = w(A) + dA(U) − dA(U) ≤ w(A) = λ4(G). Since |A − U| < |A| = α4(G), it follows by Lemma 2.1, G[A − U] is λ4-independent, a contradiction.
• (ii) The proof is similar to the first case.
• (iii) If A − x is λ4-independent for each x ∈ A, the we have dA(x) ≥ 2. Thus we may suppose that A − x has a λ4-non-trivial component for some x ∈ A. Set U = x. Now dA(x) > dA(x) and since dA(x) > 1/2(dA(x) + dA(x)) we see that dA(x) ≥ 2, as wanted.

Similar to Lemma 2.2, we can prove the following lemma. The key observation to the proof, as well as some proofs after it, is that for any edge e ∈ E(G), if λ4(G − e) < λ4(G), then any λ4-fragment of G − e contains exactly on end of e, and is a λ4-fragment of G.

Lemma 2.3. Suppose that e = uv is an edge of G, λ4(G − e) < λ4(G) and A is a λ4-atom of G − e with u ∈ A, v /∈ A.

• (i) If U is a subset of A such that G[U] is connected and G[A] − U has λ4-non-trivial component and e is not incident with U then dA(U) > dA(U).
• (ii) dG[A](x) ≥ 2 for each x(̸= u) ∈ A.

Lemma 2.4. Suppose that A is a λ4-atom and B is a λ4-fragment of G and A ∩ B ̸= ∅. Then for any component C of G[A ∩ B] either G[A] − C or G[B] − C is λ4-independent.

Proof. Suppose to contrary that G[A] − C and G[B] − C have a λ4-non-trivial component. Set U = G[C]. By Lemma 2.2 we have dA(U) > dA(U) ≥ dB−A(U) = dB(U) and dB(U) > dB(U) ≥ dA−B(U) = dA(U), a contradiction.

With the similar arguments with proof of Lemma 2.4 we have the following lemma.

Lemma 2.5. Suppose that e = uv is an edge of G, λ4(G − e) < λ4(G), A is a λ4-atom of G − e with u ∈ A, v /∈ A, B is a λ4-fragment of G, A ∩ B ̸= ∅ and e is not incident with B. Then for any component C of G[A ∩ B] either G[A] − C or G[B] − C is λ4-independent.

Lemma 2.6. Suppose that A is a λ4-atom of G, e = uv is an edge of G[A] and B is a λ4-atom of G − e. Then G[A ∩ B], G[A − B] and G[B − A] are connected.

Proof. Suppose to contrary that G[A ∩ B] is not connected. Suppose that C¹ and C² are two components of G[A ∩ B] and one of them has at least three elements, say C2. By Lemma 2.4, G[A] − C¹ has λ4-non-trivial component. This contradicts Lemma 2.4 contradicting. Thus all components of G[A ∩ B] have at most 2 vertices. Suppose that C is a component of G[A ∩ B]. Thus G[A] − C¹ and G[B] − C² are λ4-nontrivial, a contradiction and so G[A ∩ B] is connected. Now suppose that G[A − B] is not connected. Suppose that C¹ and C² are two components of

G[A-B]. Suppose that one of the component has at least four elements, say \(C_2\). Then G[A]-C and \(G[\overline{B}]-C\) is \(\lambda_4\)-non-trivial. This contradicts Lemma 2.4. Now suppose that all components has at most three elements. Now G[A]-C and \(G[\overline{B}]-C\) are \(\lambda_4\)-non-trivial, where C is a component of G, a contradiction. Similarly we can show that G[B-A] is connected.

Lemma 2.7. Suppose that A is a \(\lambda_4\)-atom of G, e = uv is an edge of G[A] and B is a \(\lambda_4\)-atom of G - e. Then |A - B| = 3 and \(|A \cap B| = 3\).

Proof. Suppose that \(|A \cap B| \leq 2\). Thus G[A - B] and G[B - A] are \(\lambda_4\)-non-trivial. This contradict Lemma 2.4. Now suppose that \(|A \cap B| \geq 4\). Thus \(G[A \cap B]\) is \(\lambda_4\)-non-trivial. Also since \(G[\overline{A}]\) and \(G[\overline{B}]\) are connected, it follows that \(G[\overline{A} \cup \overline{B}] = G[\overline{A} \cap B]\) is connected. Taking \(F = A \cap B\) in Lemma 2.1. Noting that \(|F| = |A \cap B| < |A| = \alpha_4(G)\) and since A is an \(\lambda_4\)-atom and \(e \in A\) we have \(w(A) = w(B) = \lambda_4(G)\). Since A is an atom, it follows that A is connected and there is an edge between A - B and \(\overline{A - B}\). Thus \(w(A \cap B) > \lambda_4(G)\). Now by equation (1) \(w(A \cap B) + w(A \cup B) \leq w(A) + w(B)\), and so \(w(\overline{A \cup B}) = w(A \cup B) < \lambda_4(G)\). Taking \(F = \overline{A \cup B}\) in Lemma 2.1. We see that \(G[\overline{A \cup B}]\) is \(\lambda_4\)-independent and so \(G[\overline{A \cup B}]\) is composed of some components of cardinality less than or equal 3.

Claim \(d_A(C) = d_B(C)\) and \(d_{A \cap B}(C) = 0\), where C is a component of \(G[\overline{A \cup B}]\).

Suppose that \(1 \leq |C| \leq 2\). Thus \(G[\overline{A}] - C\) is \(\lambda_4\)-non-trivial and so by Lemma 2.2, \(d_{\overline{A}}(C) \geq d_A(C)\). Also since C is a component of \(G[\overline{A \cup B}]\), it implies that \(|[C, \overline{A} - C]| = |[C, B - A - C]|\) and hence \(d_{\overline{A}}(C) = d_{B-A}(C)\). Therefore

\[d_A(C) \le d_{\overline{A}}(C) = d_{B-A}(C) = d_B(C) - d_{A \cap B}(C).\]

Similarly,

\[d_B(C) \le d_{\overline{B}}(C) = d_{A-B}(C) = d_A(C) - d_{A \cap B}(C).\]

Thus \(d_A(C) = d_B(C)\) and \(d_{A \cap B}(C) = 0\). Now suppose that |C| = 3. Assume that \(|\overline{A \cup B}| = 4\) and |A - B| = 1. Put \(A' = (A - B) \cup C\). Then G[A'] and G[A'] are subgraphs of order at least 4 and \(w(A') = w(\overline{A'}) = w(B \cup (\cup C_i)) = w(B) + d_{A-B}(\cup C_i) - d_{B-A}(\cup C_i) = \lambda_4(G)\), where \(C_i\) are components of \(G[\overline{A \cup B}]\) and \(1 \leq |C_i| \leq 2\). Thus A' is an atom and |A'| < |A|, a contradiction. Therefore we may suppose that \(|\overline{A \cup B}| \geq 5\) or \(|A - B| \geq 2\). Now with the similar arguments as above for every component C of \(G[\overline{A \cup B}]\), \(G[\overline{A}] - C\) has at least order 4, a contradiction. Thus \(|A \cap B| = 3\). Also \(|A - B| = |A| - |A \cap B| \geq 3\). If \(|A - B| \geq 4\) then A - B is a \(\lambda_4\)-non-trivial, a contradiction. Thus |A - B| = 3.

Now by Lemmas 2.6 and 2.7, we have the following result.

Lemma 2.8. Suppose that A is a \(\lambda_4\)-atom of G, e = uv is an edge of G[A] and B is a \(\lambda_4\)-atom of G - e. Then \(G[A] \cong X\), where X is a subgraph of complete graph \(K_6\).

For the rest of paper we may assume that G is \(K_3\)-free or (without triangle), \(A \cap B\) is a path of length 3, say \(P_3 = xyz\), and \(d_A(y) - 1 = d_{A - \{x,y,z\}}(y)\). Also we note that \(x \sim y \sim z\).

Lemma 2.9. Suppose that A is a \(\lambda_4\)-atom of G, e = uv is an edge of G[A] and B is a \(\lambda_4\)-atom of G - e. Then.

• (i) \(d_A(xyz) \ge d_{\overline{A}}(xyz)\).
• (ii) \(d_{A-B}(xyz) = d_{B-A}(xyz)\).
• (iii) For each vertex a of A, \(d_{\overline{A}}(a) = d_A(a) 1\).
• (iv) \(|[A \cap B, \overline{A \cup B}]| = |[A B, B A]| = 0.\)

Proof. (i) By Lemma 2.2, \(d_A(x) > d_{\overline{A}}(x)\) and so \(d_{\overline{A}}(x) \le d_A(x) - 1\). Now \(d_A(xyz) = d_{A-\{x,y,z\}}(x) + d_{A-\{x,y,z\}}(y) + d_{A-\{x,y,z\}}(z) \ge d_{\overline{A}}(x) + d_{\overline{A}}(y) + d_{\overline{A}}(z) = d_{\overline{A}}(xyz)\).

• (ii) \(d_{A-B}(xyz) = d_A(xyz) d_{A\cap B}(xyz) = d_A(xyz) \geq d_{\overline{A}}(xyz) = d_{B-A}(xyz) + d_{\overline{A\cup B}}(xyz) = d_{B-A}(xyz)\). If |B-A|=3 then B is \(\lambda_4\)-atom of G and so \(d_{B-A}(xyz) \geq d_{A-B}(xyz)\). Thus \(d_{A-B}(xyz) = d_{B-A}(xyz)\). If \(|B-A| \geq 4\) then G[B-A] is \(\lambda_4\)-non-trivial. Now by Lemma 2.2, \(d_{B-A}(xyz) \geq d_{A-B}(xyz)\) and so \(d_{A-B}(xyz) = d_{B-A}(xyz)\).
• (iii) Since \(d_A(xyz) = d_{\overline{A}}(xyz)\) by part (i), \(d_{A-\{x,y,z\}}(x) + d_{A-\{x,y,z\}}(y) + d_{A-\{x,y,z\}}(z) = d_{\overline{A}}(x) + d_{\overline{A}}(y) + d_{\overline{A}}(z)\). On the other hand \(d_{A-\{x,y,z\}}(x) = d_A(x) 1\), \(d_{A-\{x,y,z\}}(y) = d_A(y) 1\) and \(d_{A-\{x,y,z\}}(z) = d_A(z) 1\). Since \(d_{\overline{A}}(a) \le d_A(a)\), where \(a \in \{x,y,z\}\), we have \(d_{\overline{A}}(a) = d_A(a) 1\) for \(a \in \{x,y,z\}\). Now we considering the vertex set \(\{x',y',z'\}\). By replace B by \(\overline{B}\) we see that \(d_{\overline{A}}(a) = d_A(a) 1\) for \(a \in \{x',y',z'\}\).
• (iv) By taking the place B by \(\overline{B}\), \(d_{B-A}(x'y'z')=0\). Thus |[A-B,B-A]|=0. On the other hand \(|[A\cap B,\overline{A\cup B}]|=0\).

Lemma 2.10. Suppose that A is a \(\lambda_4\)-atom of G, e = uv is an edge of G[A] and B is a \(\lambda_4\)-atom of G - e. Then \(G[\overline{A \cup B}]\) is connected.

Proof. Suppose to contrary that \(G[\overline{A \cup B}]\) is disconnected and \(C_1\) and \(C_2\) are two components of \(G[\overline{A \cup B}]\). By Lemma 2.9, \(d_A(x'y'z') \geq d_{\overline{A}}(x'y'z')\), where \(x', y', z' \in A - B\). Thus \(w(C_1) < w(\overline{A \cup B}) = w(A \cup B) = w(B) + d_{\overline{A \cup B}}(x'y'z') - d_{A \cup B}(x'y'z') = w(B) + (d_{\overline{A}}(x'y'z') - d_{B - A}(x'y'z')) - (d_{B - A}(x'y'z') + d_A(x'y'z') + d_A(x'y'z') + d_{\overline{A}}(x'y'z') - 2d_{B - A}(x'y'z') \leq w(B) = \lambda_4(G)\).

Now by Lemma 2.1, \(C_1\) is \(\lambda_4\)-independent and so \(V(C_2) \leq 3\). Since \(G[B \setminus A]\) is connected, \(|B \setminus A| \geq 3\) and \(C_2\) is connected to \(B \setminus A\), we see that \(G[\overline{A}] - C_1\) has a \(\lambda_4\)-non-trivial component. Now by Lemma 2.2, we have

\[d_A(C_1) \le d_{\overline{A}}(C_1) = d_{B-A}(C_1) = d_B(C_1).\]

Similarly

\[d_B(C_1) \le d_{\overline{B}}(C_1) = d_{A-B}(C_1) = d_A(C_1).\]

Thus \(d_A(C_1) = d_B(C_1)\). Put \(A' = (A - B) \cup C_1\). Thus G[A'] and \(G[\overline{A'}]\) are connected. Also by Lemma 2.9, \(w(A') = w(A - B) + d_B(C_1) - d_{A-B}(C_1) = w(A - B) + d_B(C_1) - d_A(C_1) = w(A - B) =\)

\(w(A) + d_{A-B}(xyz) - d_{B-A}(xyz) = w(A) = \lambda_4(G)\). Thus A' is \(\lambda_4\)-fragment and since \(|A'| \le |A|\) we see that A' is also a \(\lambda_4\)-atom of G. Now \(d_{\overline{A'}}(x'y'z') = d_B(x'y'z') + d_{\cup C_i}(x'y'z') = d_{B-A}(x'y'z') + d_{A\cap B}(x'y'z') + d_{\cup C_i}(x'y'z') \ge d_{A\cap B}(x'y'z') + d_{C_1}(x'y'z') = d_A(x'y'z') + d_{C_1}(x'y'z') > d_A(x'y'z')\), where the \(C_i^s\) are component of G, a contradiction. \(\square\)

Theorem 2.1. Suppose that G is the minimally \(\lambda_4\)-connected graph. Then G is isomorphic to the Figure 1 and all the atoms of G are trivial.

Proof. Suppose that A is \(\lambda_4\)-atom of G, e = uv is an edge of G[A] and B is a \(\lambda_4\)-atom of G - e. We can apply Lemma 2.6 to A and B. Suppose that \(A \cap B = \{x, y, z\}\) and \(A - B = \{x', y', z'\}\). By Lemma 2.9 \(d_{\overline{A}}(t) = d_A(t) - 1\) for each \(t \in A\). Thus \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

Now suppose that D is \(\lambda_4\)-atom of G-xy and C is a \(\lambda_4\)-atom of \(G-y^{'}z^{'}\). We apply Lemma 2.10 to A,D and A,C. Without loss of generality we may suppose that \(A\cap D=\{z^{'},z,y\}\) and \(A\cap C=\{x,x^{'},y^{'}\}\). Set \(F_1=((B-A)-D)-C\), \(F_2=(B-A)\cap D\), \(F_3=(\overline{A\cup B})\cap (D-C)\), \(F_4=(\overline{A\cup B})-D)-C\), \(F_5=((\overline{A\cup B})\cap (C-D)\), \(F_6=(B-A)\cap C\) and \(F_7=(C\cap D)\). By Lemma 2.9 we have \(|[\{x^{'},y^{'},z^{'}\},F_1\cup F_2\cup F_6\cup F_7]|=|[\{x,y,z\},F_3\cup F_4\cup F_5\cup F_7]|=|[\{x,x^{'},y^{'}\},F_3\cup F_1\cup F_2\cup F_7]|=|[\{y,z,z^{'}\},F_4\cup F_5\cup F_6\cup F_7]|=|[\{z,z^{'},y^{'}\},F_1\cup F_6\cup F_5\cup F_7]|=|[\{x^{'},x,y\},F_2\cup F_3\cup F_4\cup F_7]|=0\).

Thus \(|[x,F_1\cup F_2\cup F_3\cup F_4\cup F_5\cup F_7]|=0\) and so \(|[x,F_6]|=|[x,\overline{A}]|=d_{\overline{A}}(a)=d_A(a)-1\geq \delta_{G[A]}-1\geq 1.\) With the same argument we have

\[|[x, F_6]| \ge 1, |[x', F_5]| \ge 1, |[y', F_4]| \ge 1, |[y, F_1]| \ge 1, |[z, F_2]| \ge 1, |[z', F_3]| \ge 1.\] (2)

Thus non of \(F_1, F_2, F_3, F_4, F_5\) and \(F_6\) are empty and \([A, \overline{A}] = [x, F_6] \cup [y, F_1] \cup [z, F_2] \cup [x', F_5] \cup [y', F_4] \cup [z', F_3]\). Also note that since \(|[F_5 \cup F_6, F_7]| \ge 1\) and \(|[F_2 \cup F_3, F_7]| \ge 1\) we have \(F_7 \ne \emptyset\). Since \(G[F_1 \cup F_2 \cup F_6] = G[B - A], G[F_5 \cup F_6 \cup F_7] = G[C - A], G[F_2 \cup F_3 \cup F_7] = G[D - A], G[F_1 \cup F_4 \cup F_5 \cup F_6] = G[\overline{A} \cup \overline{D}]\) and \(G[F_3 \cup F_4 \cup F_5 \cup F_7] = G[\overline{A} \cup \overline{B}]\) are connected without loss of generality we have

\[|[F_1, F_2]| \ge 1, |[F_2, F_3]| \ge 1, |[F_1, F_4]| \ge 1, |[F_3, F_4]| \ge 1,\]

\[||F_5, F_6|| \ge 1, ||F_1, F_6|| \ge 1, ||F_2, F_7| \ge 1, ||F_5, F_7|| \ge 1.\] (3)

Therefore we have

\[w(B) = |[xyz, x'y'z']| + |[F_1 \cup F_2 \cup F_6, F_3 \cup F_4 \cup F_5 \cup F_7]|, \tag{4}\]

\[w(D) = |[yzz', xx'y']| + |[F_2 \cup F_3 \cup F_7, F_1 \cup F_4 \cup F_6 \cup F_5]| + |[y, F_1]|, \tag{5}\]

\[w(C) = |[y', F_4]| + |[\{x, x', y'\}, \{y, z, z'\}]| + |[F_6 \cup F_5 \cup F_7, F_1 \cup F_2 \cup F_4 \cup F_3]|.\] (6)

We know that G[A] is isomorphic to the subgraph of \(K_6\). Thus either \(G[A] \cong C_6\) or G[A] is one of the graphs in Figures (2) and (3). Suppose that \(G[A] \cong C_6\). Then \(\lambda_4(G) = 2 | [xyz, x'y'z']| + 2 = 6\) and so equalities hold in (2). Also by (3), (4), (5) and (6) we have \(w(B) \geq 6\), \(w(D) \geq 6\) and \(w(C) \geq 6\). Since B, C and D are \(\lambda_4\)-fragment, we have \(w(B) = w(C) = w(D) = \lambda_4(G) = 6\). In particular, \(|[F_1, F_3]| = 0\). Now by considering \(|[F_1, A]| = [y, F_1]| = 1\) we have \(w(F_1) = 4 < \lambda_4(G)\). Now by Lemma 2.1, \(G[F_1]\) is \(\lambda_4\)-independent. Also since \(G[F_1 \cup F_2 \cup F_6]\) is connected, without loss of generality we may suppose that \(|[F_1, F_2]| = 1\). We see that \(G[F_1]\) is connected and so \(|F_1| \leq 3\). Suppose that \(|F_1| = 2\) or \(|F_1| = 3\). Put \(F = F_1 \cup x \cup y\). We have \(|F| < \alpha_4(G)\) and \(w(F) = w(F_1) - |[x, F_1]| + d_A(x) - |[y, F_1]| + d_A(y) - |[x, y]| = 4 - 0 + 2 - 1 + 2 - 1 = 6 = \lambda_4(G)\). By Lemma 2.1, G[F] is \(\lambda_4\)-independent, a contradiction. Thus \(|F_1| = 1\). Similarly, \(|F_1| = |F_2| = |F_3| = |F_4| = |F_5| = |F_6| = |F_7| = 1\).

Now suppose that G[A] is isomorphic to one of the graphs in Figure 2. We have \(\lambda_4(G) =\)2|[xyz, x'y'z']| + 2 = 8 and \(w(B) = w(D) = w(C) = \lambda_4(G) = 8\). Now by (6), \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(|F_2 \cup F_3 \cup F_4| \le 4\) and so by (3) without loss of generality we may suppose that \(|[F_1, F_6]| \le 1\). By (4), \(|[F_1 \cup F_2 \cup F_6, F_3 \cup F_4 \cup F_5 \cup F_7]| = 5\) and so by (3) we have \(|[F_1, F_4]| \le 2\). Also by (5), \(|[F_2 \cup F_3 \cup F_7, F_1 \cup F_4 \cup F_5 \cup F_6]| \le 4\) and so by (3) we have \(|[F_1, F_2]| \le 2\). Therefore \(w(F_1) = |[y, F_1]| + |[F_1, F_2]| + |[F_1, F_6]| + |[F_1, F_7]| \le 6 < 8\). Now by Lemma 2.1, \(G[F_1]\) is \(\lambda_4\)-independent. Also since \(|[F_1, F_4]| = 1\) and \(G[F_1 \cup F_4]\) is connected we conclude that \(G[F_1]\)is connected. Thus \(|F_1| \leq 3\). Suppose that \(|F_1| = 3\) and put \(F = F_1 \cup y\). G[F] and G[F] are connected and \(|F| = 4 < \alpha_4(G)\) and \(w(F) = w(F_1) + d_A(y) - |[y, F_1]| \le 6 + 2 - 1 = 7 < \lambda_4(G)\). Thus G[F] is \(\lambda_4\)-independent, a contradiction. Thus we may suppose that \(|F_1| = 1\) or \(|F_1| = 2\). If \(|F_i| = 1\) for \(1 \le i \le 7\). Since G is simple by (3) we conclude that \(|[F_1, F_6]| = |[F_1, F_2]| =\)\(|[F_1, F_4]| = 1\) and \(w(F_1) = |[y, F_1]| + |[F_1, F_6]| + |[F_1, F_2]| + |[F_1, F_4]| = 4\). Thus if we put \(F = F_1 \cup z' \cup y \cup z\) then w(F) = 8 and by \(|F| < \alpha_4(G)\), a contradiction. Thus we may suppose that \(|F_1| = |F_6| = 2\). We put \(F = F_1 \cup F_6\). Thus \(w(F) = w(F_1) + w(F_2) - |[F_1, F_6]| \le 1\)\(|[y, F_1]| + |[F_1, F_6]| + |[F_1, F_2]| + |[F_1, F_4]| + +|[F_1, F_6]| + |[F_5, F_6]| + |[F_6, x]| - |[F_1, F_6]| \le 8,\)a contradiction. Now suppose that G[A] is isomorphic to one of the graphs in Figure 3. We have \(\lambda(G) = 2|[xyz, x'y'z']| + 2 = 8 + 2 = 10\). Suppose that \(|F_1| = 3\) and put \(F = F_1 \cup y\). Thus G[F]and G[F] are connected and \(w(F) = w(F_1) - |[y, F_1]| + d_A(y) \le 8 - 1 + 2 = 10 = \lambda_4(G) = 10\) and so F is \(\lambda_4\)-independent a contradiction. Thus we may suppose that \(|F_1| = 1\) or \(|F_1| = 2\). If \(|F_1| = 2\)then by (4) we have \(|[F_1 \cup F_2 \cup F_3 \cup F_4, F_5 \cup F_6 \cup F_7]| = 5, |[F_1 \cup F_4 \cup F_5 \cup F_6, F_2 \cup F_3 \cup F_7]| = 5\)and \(|[F_1 \cup F_2 \cup F_6, F_3 \cup F_4 \cup F_5 \cup F_7]| = 6\). By (3) without loss of generality we may suppose that \(|[F_1, F_6]| = 1\), \(|[F_1, F_2]| \le 3\) and \(|[F_1, F_4]| \le 2\). Now \(w(F_1) \le 7\). Put \(F = F_1 \cup x \cup y\). Thus \(w(F) = w(F_1) - |[y, F_1]| + d_A(x) + d_A(y) - |[x, y]| \le 7 - 1 + 2 + 3 = 10\) and by \(|F| < \alpha_4(G)\)we get a contradiction. Therefore we may suppose that \(|F_i|=1\) for \(1\leq i\leq 7\). Now since G is

simple we have \[|[F_1, F_6]| = |[F_1, F_2]| = |[F_1, F_4]| = 1\] and so \(w(F_1) = 4\). Put \(F = F_1 \cup x \cup y \cup z\). Now \(w(F) \le 9 < \lambda_4(G)\), a contradiction.

Acknowledgement

The authors are very grateful to the referees for their valuable comments.

References

• [1] M. Bai, Y. Tian, and J. Yin, The super restricted edge-connectedness of direct product graphs, Parallel Process. Lett. 33(3) (2023) 2350008:1-2350008:7.
• [2] H. Cheng, R. Varmazyar, and M. Ghasemi, On k-restricted connectivity of direct product of graphs, Discrete Math. Algorithms Appl. 15(8) (2023) 2250175.
• [3] M. Ghasemi, Some results about the reliability of folded hypercubes. Bull. Malaysian Math. Sci. Soc. 44 (2021) 1093– 1099.
• [4] M. Ghasemi, On the reliability of modified bubble-sort graphs. Trans. Combiatorics. 11(2) (2022) 77–83.
• [5] A. Hellwig and L. Volkmann, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math. 308 (2008) 3265–3296.
• [6] Y.M. Hong, Q.H. Liu, and Z. Zhang, Minimally restricted edge connected graphs, App. Math. Lett. 21 (2008) 820–823.
• [7] Q.G. Liu, Y.M. Hong, and Z. Zhang, Minimally 3-restricted edge connected graphs, Discrete Appl. Math. 157 (2009) 685–690.
• [8] X.M. Liu and J. Meng, The k-restricted edge-connectivity of the data center network DCell, Appl. Math. Comput. 396 (2021) 125941.
• [9] S. Liu, C. Ouyang, and J, Ou, Sufficient conditions for optimally and super m-restricted edgeconnected graphs with given girth, Linear Multilinear Algebra. 70(6) (2020) 1146–1158.
• [10] L. Lovasz, Combinatorial Problems and Exercises, North-Holland Publishing Company, ´ 1979.
• [11] T. Ma, J. Wang, and M. Zhang, The restricted edge-connectivity of kronecker product Graphs, Parallel Process. Lett. 29(3) (2019) 1950012:1-1950012:7.
• [12] J.X. Meng, Optimally super-edge-connected transitive graphs, Discrete Math. 260 (2003) 239–248.
• [13] H. Tarakmi, H. Azanchilar, M. Ghasemi, and Gh. Azadi, n-restricted edge connectivity of m-barrel fullerene graphs, Iran J. Sci. Technol Trans. A. Sci. 45 (2021) 997–1004

• [14] Y.Q. Wang and Q. Li, Super-edge-connectivity properties of graphs with diameter 2, J. Shanghai Jiaotong Univ. 33 (6) (1999) 647–649(in Chinese)
• [15] Y.Q. Wang and Q. Li, Sufficient conditions for a graph to be maximally restricted edgeconnected, J. Shanghai Univ. 35 (8) (2001) 1253–1255(in Chinese).
• [16] J.M. Xu and K.L. Xu, On restricted edge-connectivity of graphs, Discrete Math. 243 (2002) 291–298.
• [17] Z. Zhang and J.X. Meng, Restricted edge connectivity of edge transitive graphs, Ars Combinatorica. LXXVIII (2006) 297–308.
• [18] Z. Zhang and J.J. Yuan, Degree conditions for restricted-edge-connectivity and isoperimetricedge-connectivity to be optimal, Discrete Math. 307 (2007) 293–298.