EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 4, 2023, 2786-2797 ISSN 1307-5543 – ejpam.com Published by New York Business Global Prime Graph Generation through Single Edge Addition: Characterizing a Class of Graphs Ayesha Alorini1,2, Aymen Ben Amira1, Mohammad Alzohairi1, Moncef Bouaziz1,∗ 1 Department of Mathematics, College of Sciences, King Saud University, Riyadh, Saudi Arabia 2 Department of Mathematics, College of Sciences, Imam Mohammad Ibn Saud University, Riyadh, Saudi Arabia Abstract. A graph G consists of a finite set V (G) of vertices with a collection E(G) of unordered pairs of distinct vertices called edge set of G. Let G be a graph. A set M of vertices is a module of G if, for vertices x and y in M and each vertex z outside M , {z, x} ∈ E(G) ⇐⇒ {z, y} ∈ E(G). Thus, a module of G is a set M of vertices indistinguishable by the vertices outside M . The empty set, the singleton sets and the full set of vertices represent the trivial modules. A graph is indecomposable if all its modules are trivial, otherwise it is decomposable. Indecomposable graphs with at least four vertices are prime graphs. The introduction and the study of the construction of prime graphs obtained from a given decom- posable graph by adding one edge constitue the central points of this paper. 2020 Mathematics Subject Classifications: 05C60 Key Words and Phrases: Module, Prime, Decomposable, Prime Frame, Isomorphism. 1. Introduction Our notations and terminology follow [1]. All graphs mentioned in this paper are finite. Without loops and multiple edges, these graphs are called simple graphs. A graph G consists of a finite set V (G) of vertices called vertex set with a collection E(G) of pairs of distinct vertices (edge set of G). Such a graph is denoted by (V (G), E(G)) (Simply (V,E)). An empty graph is a graph without edges while a complete graph is a graph with all possible edges. Two distinct vertices u and v of a graph G are adjacent if {u, v} ∈ E(G). An edge {u, v} of G is denoted by uv while u and v are called endpoints of the edge uv. Two distinct edges e and e′ of a graph G are adjacent edges if they have a common endpoint. A neighbor of a vertex u in a graph G is a vertex adjacent to u, the neighborhood of u denoted by NG(u) ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i4.4829 Email addresses: aaalorini@imamu.edu.sa (A. Alorini), abenamira@ksu.edu.sa (A. Ben Amira), mzohairi@gmail.com (M. Alzohairi), mbouaziz@ksu.edu.sa (M. Bouaziz) https://www.ejpam.com 2786 © 2023 EJPAM All rights reserved. M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2787 is the set of neighbors of u and the neighborhood of a subset X of V (G) represented by NG(X) is the union of the neighborhoods of every vertex in X. The degree of u denoted by dG(u) is dG(u) = |NG(u)|. The complement of a graph G is the graph G such that V (G) = V (G) and E(G) = {{u, v} : u ̸= v ∈ V (G), {u, v} /∈ E(G)}. For undefined notions and notations in the graph theory, see [8]. In particular, a graph H = (W,F ) is a subgraph of a graph G = (V,E) if W ⊆ V and F ⊆ E. Given a subset X of the vertex set of a graph G = (V,E), the subgraph G[X] = (X,E ∩ {xy, x ̸= y ∈ X}) is called the subgraph induced by X. The subgraph G[V (G) \X] is denoted by G−X. Considering a vertex x, the subgraph G− {x} is also denoted by G− x. For a vertex u outside a vertex subset X of a graph G, u ∼G X denotes when u is either adjacent to all or none of the elements of X. In a graph G, a vertex subset M is a module of G if every vertex outside M is either adjacent to all or none of the elements of M . This concept was introduced in [6]. The empty set, the singleton sets and the full set V (G) of vertices are trivial modules. A module of a graph G distinct from V (G) is a proper module of G. A graph is indecomposable if all its modules are trivial, otherwise it is decomposable. Clearly, all graphs with at most two vertices are indecomposable. Given a 3-vertex graph G, if G is complete or empty, then each 2-element vertex subset is a non-trivial module of G, otherwise G has a unique non- trivial module {u, v} where uv is the unique edge of G or G. Thus, all 3-vertex graphs are decomposable. Indecomposable graphs with at least four vertices are called prime graphs. An isomorphism f from a graph G = (V,E) onto a graph G′ = (V ′, E′) is a bijection from V onto V ′ such that for all x, y ∈ V , xy ∈ E ⇔ f(x)f(y) ∈ E′. We denote G ≃ G′ the graphsG andG′ which are called isomorphic if there is an isomorphism fromG ontoG′. In order to state our theorem, we introduce the following new graphs, along with some known graphs. Recall the known small graphs used in this paper. First, the graph P4 = ({v1, v2, v3, v4}, {v1v2, v2v3, v3v4}) (illustrated in Figure 1). Second, the graph β = ({a, a′, x, x′, y}, {ax′, ay, aa′, a′x′, a′y, xy}) (shown in Figure 2). Finally, the Taurus (resp. the House) is the graph with the vertex set {a, x1, x′1, x2, x′2} and the edge set {ax′1, ax′2, x′1x′2, x1x′1, x2x′2}, (resp. {ax′1, ax′2, x′1x′2, x1x′1, x2x′2, x1x2}) as illustrated in Figure 3. v1 v2 v3 v4 Figure 1: P4 x′ a a′ y x Figure 2: β M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2788 x1 x2 x′ 1 x′ 2 a Taurus x1 x2 x′ 1 x′ 2 a House Figure 3: Taurus and House Let’s define the following two graph families: Definition 1. Let k and q be two non-negative integers with k ≥ 2. A Palace Pk,q is a graph (V,E) satisfying the following: There is a ∈ V such that, by denoting Z = NPk,q (a) and X = V \ (Z ∪ {a}), |Z| ≥ k, |X| = k and |Z|−k = q. Moreover, by denoting X = {x1, x2, . . . , xk}, there is a k-element subset X ′ = {x′1, x′2, . . . , x′k} of Z such that Pk,q[X ′] is a complete graph, the set of edges between X and X ′ is {xix′i : 1 ≤ i ≤ k} and the subset Y = Z \X ′ satisfies the following conditions: (i) For every y ∈ Y , Pk,q[{a, y} ∪X ′] is a complete graph. (ii) For every y ∈ Y , either 1 < |NPk,q [X∪{y}](y)| < k or (|NPk,q [X∪{y}](y)| ∈ {1, k} and ∃ z ∈ Y \ {y} such that zy /∈ E). (iii) For any y1 ̸= y2 ∈ Y , NPk,q [X∪y1](y1) ̸= NPk,q [X∪y2](y2). x1 x2 . . . xkX Yx′ 1 x′ 2 . . . x′ k X ′ a y1 yq. . . xi xjxs Figure 4: Palace Pk,q (k ≥ 2, q ≥ 0) Definition 2. Let k ≥ 2 and q be two non-negative integers. A Palace βk,q is a graph obtained from a palace Pk,q by replacing the module {a} with the module {a, a′} where βk,q[{a, a′}] is isomorphic to the graph K2, as illustrated in Figure 5. Notation: The family of graphs isomorphic to the graph β or a palace βk,q, for some k ≥ 2 and q ≥ 0, M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2789 x1 x2 . . . xkX Yx′ 1 x′ 2 . . . x′ k X ′ a a′ y1 yq. . . . . . xi xjxs Figure 5: Palace βk,q (k ≥ 2, q ≥ 0) is denoted by B. 1.1. Gallai’s decomposition Let G = (V,E) be a graph. An equivalence relation is denoted by ∼= between the pairs of vertices of G for x and y as well as u and v. xy ∈ E if and only if uv ∈ E defines {x, y} ∼= {u, v}. To recall the basic properties of the modules, we introduce the following notation: Given a graph G on the vertex set V and two disjoint vertex subsets X and Y of V , X and Y are equivalent (X ∼ Y ) if, for any vertices x and x′ in X and y and y′ in Y , {x, y} ∼= {x′, y′}. Proposition 1. Let G be a graph on the set of vertices V . (i) ∅, V and {u} where u ∈ V are modules of G. (ii) Considering a non-empty vertex subset W of V , if M is a module of G, then M ∩W is a module of G[W ]. (iii) If M and N are modules of G, then M ∩N is a module of G. (iv) If M and N are modules of G such that M ∩N ̸= ∅, then M ∪N is a module of G. (v) If M and N are modules of G such that M \N ̸= ∅, then N \M is a module of G. (vi) If M and N are disjoint modules of G, then M ∼ N . A partition P of the vertex set V (G) of a graph G is a modular partition of G if all its elements are modules of G. Based on the last assertion of Proposition 1, it follows that M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2790 the elements of P may be considered as the vertices of a new graph. The quotient of G by P is G/P defined on P as follows: for the distinct elements X and Y of P, XY ∈ E(G/P) if xy ∈ E(G) for every x and y where x ∈ X and y ∈ Y . A module X of a graph G is a strong module of G if, for every module Y of G, X ∩ Y ̸= ∅. Hence, either X ⊆ Y or Y ⊆ X. If | V (G) |≥ 2, then P(G) denotes the family of maximal proper strong modules of G, equipped with the inclusion. The following theorem shows Gallai’s decomposition result. Theorem 1. [4, 5] Let G be a graph with at least two vertices. The class P(G) is a modular partition of G and the quotient G/P(G) is a prime, complete or empty graph. Taking in consideration a graph G with more than one vertex, the elements of P(G) are the modular components of G, P(G) is its canonical partition and the quotient G/P(G) is its frame. 2. Preliminary Results 2.1. Prime graphs and their prime subgraphs Ehrenfeucht and Rozenberg [3] constructed prime subgraphs of a larger size than a given prime subgraph as follows. Let G = (V,E) be a graph. Given a proper subset X of V such that G[X] is prime, consider the following subsets of V \X: • Ext(X) is the set of x ∈ V \X such that G[X ∪ {x}] is prime. • ⟨X⟩ is the set of x ∈ V \X such that X is a module of G[X ∪ {x}]. • For u ∈ X, X(u) is the set of x ∈ V \X such that {x, u} is a module of G[X ∪ {x}]. The family of the non-empty elements of the union {Ext(X), ⟨X⟩} ∪ {X(u) : u ∈ X} is denoted by PX . Lemma 1. [3] taking into account a graph G = (V,E), consider a proper subset X of V such that G[X] is prime. The family PX realizes a partition of V \X. Moreover, the following assertions hold. 1) Let u ∈ X. For x ∈ X(u) and y ∈ V \ (X ∪X(u)), if G[X ∪ {x, y}] is not prime, then {u, x} is a module of G[X ∪ {x, y}]. 2) For x ∈ ⟨X⟩ and y ∈ V \ (X ∪ ⟨X⟩), if G[X ∪ {x, y}] is not prime, then X ∪ {y} is a module of G[X ∪ {x, y}]. 3) For two distinct vertices x and y in Ext(X), if G[X ∪{x, y}] is not prime, then {x, y} is a module of G[X ∪ {x, y}]. D. P. Sumner obtained the following result: Lemma 2. [7] If G is a prime graph, then G contains a path P4 as an induced subgraph. M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2791 2.2. Prime graphs and their subgraphs with prime frames The following notations introduced by Y. Boudabbous and P. Ille [2] generalize those mentioned in the previous Section. Given a proper vertex subset X of a graph G such that |X| ≥ 4 and the frame of G[X] is prime, consider the following subsets of V (G) \X: • ⟨X⟩ is the set of x outside X such that X is a module of G[X ∪ {x}]. • Ext(X) is the set of x outside X such that the frame of G[X ∪ {x}] is prime and {x} ∈ P(G[X ∪ {x}]). • For each C in P(G[X]), X(C) is the set of x outside X such that the frame of G[X ∪ {x}] is prime and C ∪ {x} ∈ P(G[X ∪ {x}]). The family of the non-empty elements of the union {Ext(X), ⟨X⟩} ∪ {X(C) : C ∈ P(G[X])} is denoted by QX . The following theorem is essential to prove some results in this paper. Theorem 2. [2] Taking into account a graph G = (V,E), consider a proper vertex subset X of G with at least four vertices such that the frame of G[X] is prime. 1) The family QX forms a partition of V \X. 2) If the graph G is prime, then there are two vertices x and y outside X such that the frame of G[X ∪ {x, y}] is prime and {x}, {y} ∈ P(G[X ∪ {x, y}]). More precisely: (i) If ⟨X⟩ ≠ ∅, then there is a vertex x in ⟨X⟩ and a vertex y outside X ∪ ⟨X⟩ such that the frame of G[X ∪ {x, y}] is prime and {x}, {y} ∈ P(G[X ∪ {x, y}]). (ii) Given an element C of P(G[X]), if |C ∪X(C)| ≥ 2 and Ext(X) = ∅, then there is a vertex x in X(C) and a vertex y outside X ∪ X(C) such that the frame of G[X ∪ {x, y}] is prime and {x}, {y} ∈ P(G[X ∪ {x, y}]). 3. Main result Proposition 2. Let k and q be non-negative integers with k ≥ 2. Let G be a graph. If G is a Pk,q graph, then G is prime. Proof. Let k and q be non-negative integers with k ≥ 2. Let G be a Pk,q graph. First, if q = 0, then G is a Pk,0 graph. Assume that |Xk| = |X ′ k| = k where Xk = {x1, x2, ..., xk} and X ′ k = {x′1, x′2, ..., x′k} are M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2792 two disjoint sets. Using the induction on k (k = |X|), we prove that G is a prime graph. On the one hand, if k = 2, then G is the Taurus (resp. the House) where x1 is non- adjacent ( resp. adjacent) to x2. Thus, G is a prime graph. On the other hand, k ≥ 2. Assume that, for every Pk,0 graph H, H is prime. We prove that every Pk+1,0 graph H ′ is prime. Let Xk+1 = Xk ∪ {xk+1} and X ′ k+1 = X ′ k ∪ {x′k+1} such that x′k+1xk+1 ∈ E(H ′) and S = Xk ∪X ′ k ∪{a}. Based on Definition 1, there is a Pk,0 graph H1 such that H ′[S] ≃ H1. Then, by the induction hypothesis, H ′[S] is prime. Using the definition of the graph H ′, {a, x′k+1} is adjacent to X ′ k but non-adjacent to Xk. Thus, x′k+1 ∈ S(a). According to the definition of the graph H ′, xk+1 is adjacent to x′k+1 but non-adjacent to the vertex a. Consequently, {a, x′k+1} is not a module in G[S ∪ {xk+1, x ′ k+1}]. Based on assertion 1 of Lemma 1, H ′ is prime. Second, q ≥ 1. Let a ∈ V . Consider X, X ′, Y and Z as mentioned in Definition 1. Suppose W = X ∪X ′ ∪ {a}. Y ̸= ∅. On the contrary, consider a non-trivial module M of G. The fact that G[W ] is prime implies that M ∩W = W , M ∩W is empty or M ∩W is a singleton. Firstly, if M∩W = W , then W ⊂ M . Let y ∈ V \M . As a consequence, y ∼ W . Thus, |NG[X∪{y}](y)| = k and by definition y is unique in Y . There is z ∈ Y \{y} such that zy /∈ E and there is x ∈ X such that zx /∈ E and, for all x′ ∈ X ′, zx′ ∈ E, which is a contradiction. Secondly, if M∩W = ∅, then M ⊂ Y , which contradicts the fact that NG[X∪{y1}](y1) ̸= NG[X∪{y2}](y2) for any y1 ̸= y2 ∈ Y . Thirdly, there is α in V such that M ∩W = {α}. Let t ∈ M \ {α}, t ∈ Y . Then, there is x ∈ X such that xt ∈ E. α ̸= a because, for all x ∈ X, ax /∈ E and tx ∈ E. α /∈ X since, for every x ∈ X, ax /∈ E and at ∈ E. Otherwise, there is x′ ∈ X ′ such that α = x′. Then, there is x ∈ X such that xx′ /∈ E and ax′ ∈ E, which is a contradiction. Thus, α /∈ X ′. Therefore, G is prime. Lemma 3. Let H be a decomposable graph with a prime frame. For any module M ∈ P(H), there are two distinct vertices y, z ∈ V (H) \M such that y ∈ NH(M), z /∈ NH(M) and yz /∈ E(H). Proof. Let H = (V,E) be a decomposable graph with a prime frame. Let M ∈ P(H) be a module of H. As H has a prime frame, NH(M) ̸= ∅ and V \ (M ∪NH(M)) ̸= ∅. On the contrary, suppose that, for any y ∈ NH(M) and z /∈ (M ∪ NH(M)), yz ∈ E. It follows that ∀y ∈ NH(M) and ∀t ∈ V \NH(M), yt ∈ E. Then, {NH(M), (V \NH(M))} M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2793 is a modular partition of H with two elements. As M ̸= V \NH(M), M ⊂ V \NH(M), which contradict the fact that M ∈ P(H). To prove the main result, we use the following five lemmas. Lemma 4. Let G be a decomposable graph with a prime frame such that G ∈ B. If e is an edge in G, then G+ e is a decomposable graph. Proof. Let G ∈ B and e ∈ G. Consider the graph H = G+ e. Firstly, if |V (G)| = 5, then G ≃ β. If e is one of the edges x′x and x′y, then {a, a′} is still a module in G+ e. Thus, G+ e is a decomposable graph. Otherwise, e = ax or e = a′x. Without loss of generality, we add ax. Then, {x, x′, a′, y} is a non-trivial module. As a result, G+ e is a decomposable graph. Secondly, |V (G)| ≥ 6. If the edge e = αβ where α and β are two vertices in X ∪ Y , then {a, a′} is still a module in G+ e. Thus, G+ e is a decomposable graph. Otherwise, e = ax or e = a′x for x ∈ X. Assume, without loss of generality, that e = ax and there is exactly one vertex x′ in X ′ such that xx′ ∈ E. Thus, {ax′} is a module in G+ e. Therefore, G+ e is a decomposable graph. Lemma 5. Let G be a decomposable graph with a prime frame containing only one non- trivial module M . If G[M ] = K2, then there is an edge e in G such that G+ e is prime. Proof. Let G = (V,E) be a decomposable graph with a prime frame containing only one non-trivial module M = {a, a′} such that G[M ] = K2 and e ∈ E(G). Consider H = G+ e. Based on Lemma 3, there is x /∈ NG(M) and x′ ∈ NG(M) such that xx′ /∈ E(G). If e = ax, then H[{x, a, x′, a′}] is a P4. H − a = G − a is prime. As H[{x, a, x′, a′}] is a path P4, in H, a /∈ ⟨V \ {a}⟩, a /∈ (V \ {a}) (a′), a /∈ (V \ {a}) (x) and a /∈ (V \ {a}) (x′). If H is not prime, then there is y in V \ {a, a′, x, x′} such that a ∈ (V \ {a}) (y). Hence, a′y /∈ E(H) because a′a /∈ E(H). Thus, ya /∈ E(H) and {xy, x′y} ⊆ E(H). In this case, we choose the graph H ′ = G + e′ where e′ = ay. Notice that H ′[{a, a′, x, x′, y}] is a Taurus. H ′ − a = G − a is prime. Since H ′[{a, a′, x, x′, y}] is a Taurus, a /∈ ⟨V \ {a}⟩ and a /∈ (V \ {a}) (α) with α ∈ {a′, x, x′, y}. We prove that H ′ is prime using contradiction. Assume that H ′ is not prime. Then, there is z in V \ {a, a′, x, x′, y} such that a ∈ (V \ {a}) (z). Moreover, za′ /∈ E(H ′) because aa′ /∈ E(H ′). As {a, a′} is a module in G, za /∈ E(H ′), {x′z, yz} ⊆ E(H ′) and xz /∈ E(H ′). Knowing that za /∈ E(H ′) and zy ∈ E(H ′) contradict the fact that {a, y} is a module in H, H ′ is prime. Lemma 6. Let G be a decomposable graph with a prime frame containing only one non- trivial module M . If G[M ] = K2 and G /∈ B, then an edge e exists in G such that G + e is prime. M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2794 Proof. Let G = (V,E) be a decomposable graph with a prime frame containing only one non-trivial module M = {a, a′} such that G[M ] = K2 and G /∈ B. Let e ∈ E(G). Consider that H = G+ e. Suppose Z = NG(M), X = V \ (Z ∪ {a, a′}). Let W = V \ {a}. Since the frame of G is prime, X ̸= ∅ and Z ̸= ∅. Let B = {b : b ∈ X and bz /∈ E, ∀z ∈ Z} ( B ̸= X because the frame is prime). Firstly, B ̸= ∅. As G− a is prime, there is y ∈ B and x ∈ X \B such that xy ∈ E. Consider H = G+ e where e = ay. Notice that G− a = H − a is prime. Knowing that, ax /∈ E(H) and aa′ ∈ E(H), a /∈ ⟨W ⟩ in H. As ya ∈ E(H) and ya′ /∈ E(H), a /∈ W (a′) in H. Since, for all β ∈ Z, yβ /∈ E(H) and ya ∈ E(H), a /∈ W (β) in H. Knowing that, for all α ∈ X \ {y}, a′a ∈ E(H) and a′α /∈ E(H), a /∈ W (α) in H. Given that xa /∈ E(H) and xy ∈ E(H), a /∈ W (y) in H. Thus, using Lemma 1 in H, a ∈ Ext(W ). Therefore, H = G+ e is prime. Secondly, B = ∅. Distinguish two cases: First, assume that there is x ∈ X where, for all x′ ∈ Z, {a, x′} is not a module in H = G+ ax. Notice that H − a = G− a is prime. As X ̸= ∅ and aa′ ∈ E(H), a /∈ ⟨W ⟩ in H. Knowing that, for all t ∈ X \ {x}, a′t /∈ E(H) and a′a ∈ E, a /∈ W (t) in H. Since a′a ∈ E(H) and a′x /∈ E(H), a /∈ W (x) in H. Given that, for all x′ ∈ Z, {a, x′} is not a module in H, a /∈ W (x′) in H. As xa ∈ E(H) and xa′ /∈ E(H), a /∈ W (a′) in H. As a consequence, based on by Lemma 1, a ∈ Ext(W ). Therefore, H is prime. Second, assume that, for all x ∈ X, there is x′ ∈ Z such that {a, x′} is a new module in H = G+ ax. Since a′a ∈ E(H) and xa ∈ E(H), a′x′ ∈ E(H) and x′x ∈ E(H). We show that, for all t ∈ V \ {a, a′, x, x′}, t ∼H {a, a′, x′}. Indeed, as {a, a′} is a module in G, for all t ∈ V \{a, a′}, t ∼G {a, a′}. Hence, t ∼H {a, a′}. Given that {a, x′} is a module in H, for all t ∈ V \ {a, a′, x, x′}, t ∼H {a, x′}. Thus, for all t ∈ V \ {a, a′, x, x′}, t ∼H {a, a′, x′}. Let X ′ be the greatest clique of Z (i.e. G[X ′] is a complete graph) such that X ′ = {x′ : x′ ∈ Z and |NG[X∪{x′}](x ′)| = 1} and X ′′ = Z \X ′. As G − a is prime, for all x ∈ X, there is a unique x′ ∈ X ′ such that xx′ ∈ E(G). As a result, |X| = |X ′|. If X ′′ = ∅, then G is a βk,0 graph, which contradicts the fact that G /∈ B. Otherwise, X ′′ ̸= ∅ and q ≥ 1. Since G is not a βk,q graph and G − a = H − a is prime, M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2795 G− a is not a Pk,q graph and k ≥ 3. We distinguish two subcases. In the first subcase, there is y ∈ X ′′ such that |NG[X∪{y}](y)| = 1 (resp. |NG[X∪{y}](y)| = k) and ∀t ∈ X ′′ \ {y}, ty ∈ E. Thus, y ∈ X ′, which contradicts the fact that X ′ is the greatest clique of Z (resp. y ∈ ⟨V \ {y}⟩, which contradicts the fact that G− a is prime). In the second subcase, there is y ̸= z ∈ X ′′ such that NG[X∪{y}](y) = NG[X∪{z}](z), so {y, z} is a non-trivial module in G− a, which contradicts the fact that G− a is prime. Lemma 7. Let G be a decomposable graph with a prime frame containing only one non- trivial module M . If G[M ] is a prime graph, then there is an edge e in G such that G+ e is prime. Proof. Let G be a decomposable graph on V with a prime frame containing only one non-trivial module M such that G[M ] is a prime graph. Suppose a ∈ M and X = V \{a}. Since the frame of G is prime and the only non-trivial module is M , there is b ∈ V \M such that b /∈ NG(M). Consider e = ab and H = G+ e. It’s clear that H − a = G− a is a graph with a prime frame having only non-trivial module M \ {a}. As b /∈ NH(M \ {a}) and ab ∈ E(H), a /∈ X(M \ {a}) in H. Given that G[M ] is prime, there are two vertices y, z ∈ M \ {a} such that ya ∈ E(G) and za /∈ E(G). Thus, a /∈ ⟨X⟩ in H. For all t ∈ (V \ M), t ∈ NG(M) or t /∈ NG(M). If t ∈ NG(M), then zt ∈ E(G). As a result, a /∈ X(t) in H. If t /∈ NG(M), then yt /∈ E(G). Thus, a /∈ X(t) in H. Therefore, using assertion 1 of Theorem 2, a ∈ Ext(X) in H. Based on assertion 2 of Theorem 2, if N ∈ P(H) where N is a non-trivial module, then N is a non-singleton module of H[M \ {a}]. Hence, N is a module of H − a. Moreover, a ∼H N . Then, a ∼G N contradicts the fact that G[M ] is prime. Consequently, H does not contain any non-trivial module. Therefore, H is a prime graph. Lemma 8. Let G be a decomposable graph with an empty frame containing only one non- trivial module M . If |M | = |V (G)| − 1 and G[M ] is a prime graph, then an edge e exists in G such that G+ e is prime. Proof. Let G be a decomposable graph on V with an empty frame containing only one non-trivial module M such that V (G) = M ∪ {b} and G[M ] is a prime graph. Let P = (x1, x2, . . . , xk) be the longest prime path in G[M ] with length k. Using Lemma 2, k ≥ 4. Consider e = bx1 and H = G + e. H − b = G − b = G[M ] is a prime graph. As H[{b, x1, x2, . . . , xk}] is a path of a length greater than 4, H[{b, x1, x2, . . . , xk}] is prime. Hence, b /∈ ⟨M⟩ in H and b /∈ M(xi) in H for all 1 ≤ i ≤ k. If H is not prime, then, using Lemma 1, there is t ∈ M \ {x1, x2, . . . , xk} such that b ∈ M(t). Thus, H[{t, x1, x2, . . . , xk}] = G[{t, x1, x2, . . . , xk}] is a path of length k + 1, which is a contra- diction. As a consequence, based on Lemma 1, b ∈ Ext(M). Therefore, H is a prime graph. Our main result is the following theorem: M. Bouaziz et al. / Eur. J. Pure Appl. Math, 16 (4) (2023), 2786-2797 2796 Theorem 3. Let G be a decomposable graph with at least 4 vertices having exactly one non-trivial module M . There is an edge e in G such that G + e is a prime graph if and only if one of the following assertions holds. (i) G has a prime frame and G[M ] is a prime graph or K2. (ii) G has a prime frame, G[M ] is K2 and G /∈ B. (iii) G has an empty frame and G[M ] is a prime graph with |M | = |V (G)| − 1. Proof. Let G be a decomposable graph with at least 4 vertices having exactly one non-trivial module M . On the one hand, if G has a prime frame, then G[M ] is K2, K2 or prime. First, if G[M ] = K2, then, according to Lemma 5, there is an edge e in G such that G+ e is prime. Second, if G[M ] = K2 and G /∈ B, then, based on Lemma 6, there is an edge e in G such that G+ e is prime. Third, if G[M ] is a prime graph, then, using Lemma 7, there is an edge e in G such that G+ e is prime. On the other hand, if G has an empty frame and V (G) = M ∪ {b} where G[M ] is a prime graph, then, based on Lemma 8, there is an edge e in G such that G+ e is prime. Inversely, assume that there is e in G where G+ e is prime. It’s clear that the frame of G is not complete. On the one hand, if the frame of G is prime since M is the only non-trivial module in G, then M does not contain any non-trivial module. Thus, G[M ] is a prime graph or G[M ] ∈ {K2,K2}. Assume that G[M ] = K2. As G + e is prime, the Lemma 4 implies G /∈ B. On the other hand, if the frame is empty knowing that each element of P(G) is a module of G and G contains only one non-trivial module M , then V \ M is a module. Given that M is the unique non-trivial module, V \M is a trivial module. Thus, V \M is a singleton. Therefore, the frame of G is isomorphic to K2, G[M ] is a prime graph and |M | = |V (G)| − 1. Acknowledgements The authors would like to extend their sincere appreciations to the Researchers Sup- porting Program for its funding of this research through the Researchers Supporting REFERENCES 2797 Project number (RSPD2023R1063). The authors are pleased to thank the anonymous referees for their careful reading and helpful suggestions. The authors are grateful to Youssef Boudabbous for suggesting the problem for this research paper. References [1] JA Bondy. Basic graph theory: paths and circuits. Handbook of combinatorics, 1:3–10, 1995. [2] Y Boudabbous and P Ille. Cut-primitive directed graphs versus clan-primitive directed graphs. Adv. Pure Appl. Math, 1:223–231, 2010. [3] A Ehrenfeucht and G Rozenberg. Primitivity is hereditary for 2-structures, fundamen- tal study. Theoret. Comput. Sci, 3(70):343–358, 1990. [4] T Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar, 18:25–66, 1967. [5] F Maffray and M Preissmann. A translation of Tibor Gallai’s paper: Transitiv orien- tierbare Graphen. In: Perfect graphs, J.L. Ramirez-Alfonsin and B.A. Reed Eds., J. Wiley, pages 25–66, 2001. [6] J Spinrad. P4-trees and substitution decomposition. Discrete Applied Mathematics, 3(39):263–291, 1992. [7] D P Sumner. Graphs indecomposable with respect to the X-join. Discrete Mathematics, 6(39):281–298, 1971. [8] D West. Introduction to Graph Theory, second ed. Prentice Hall, 2001.