Journal of Indian Acad. Math.  
ISSN: 0970-5120  
Vol. 48, No. 1 (2026) pp. 40–46.  
EDGE STABLE SETS IN GRAPH  
B. M. Kakrecha1, H. M. Makadia2, D. D. Pandya3,  
S. G. Sonchhatra4, and N. D. Abhangi5  
Abstract. An edge set F of E(G) is an edge stable set if each vertex v ∈ V (G) has  
at least one incident edge e such that e ∈ F. An edge H-dominating set is defined and  
discussed in [5]. The maximal edge stable set is a minimal edge H-dominating set. The  
maximal edge stable set with minimum cardinality is an edge stability number αe(G). The  
upper bound of αe(G) is obtained using an edge covering number α1(G). The effect of a  
vertex(edge) removal operation on αe(G) is observed. The inequality chain corresponding  
these extreme edge parameters is discussed.  
Keywords: edge stable set, edge cover, edge H-dominating set.  
2010 AMS Subject Classification: 05C70, 05C05.  
1. Introduction  
Let G = (V, E) be a finite, simple, undirected graph. The vertex set of G is denoted  
by V (G) (or simply V ) and edge set by E(G) (or E). Each edge e ∈ E is an unordered  
pair of distinct vertices of V. If an edge e = uv then we say that a vertex u is adjacent  
to vertex v or the vertices u and v are neighbors and that e is incident to u and v.  
A subgraph H of G is a graph such that V (H ) ⊆ V (G) and E(H ) ⊆ E(G). For a  
vertex v ∈ V (G), the graph G − v is called a vertex-deleted subgraph of G. If vu ∈ E(G)  
then G − vu is called an edge-deleted subgraph of G.  
The degree of a vertex v (denoted by deg(v)) is equal to the number of vertices that  
are adjacent to v. If there is a vertex v ∈ V (G) such that deg(v) = 0 then v is called  
an isolated vertex. If deg(v) = 1 then v is called a pendent vertex. An edge e = uv is an  
isolated edge of G if deg(u) = 1 and deg(v) = 1 in G also e = uv is a pendent edge of G  
if the degree of exactly one of u and v is 1 in G. The minimum degree of the graph G is  
denoted by δ(G). |V| denotes the cardinality of V.  
A concept called an edge stable set of graph [4] is considered in this paper. The various  
results of an edge variant of the graph called edge H-domination have been discussed  
and proved in [5]. In this paper, the relations between these two edge variants namely  
edge H-domination and edge stability are observed and proved. The change in the edge  
stability number of the graph is observed under the operation vertex(edge) removal from  
the graph. The maximal edge stable set with minimum cardinality is defined. The edge  
parameters considered in this paper are expressed in terms of an inequality chain.  
Example 1.1. Consider the following graph with vertices 1, 2, 3, 4, 5, 6 and edges 12,  
23, 34, 45, 53, 36 and 16.  
40  
EDGE STABLE SETS IN GRAPH  
41  
Figure 1. Graph G with 6 vertices  
Some examples of edge stable sets of the graph G are  
{16, 23, 34}, {12, 36, 45}, {16, 23, 34, 35}.  
Obviously, every subset of an edge stable set is an edge stable set.  
An edge stable set exists only in those graphs G for which δ(G) ≥ 1. In this paper, we  
consider only those graphs which has δ(G) ≥ 2.  
Definition 1.2. (maximal edge stable set) An edge stable set F is a maximal edge stable  
set if F ∪ {e} is not an edge stable set for any edge e ∈ E − F.  
Example 1.3. The edge stable set F = {16, 23, 34, 35} is a maximal edge stable set of  
the graph given in figure 1.  
Definition 1.4. An edge stable set with maximum cardinality is a maximum edge stable  
set. The cardinality of a maximum edge stable set is the edge stability number of G,  
denoted by αe(G).  
2. Upper bound of an edge stability number  
Definition 2.1. [3] A subset F of E(G) is said to be an edge cover of G if every vertex  
of G is an end vertex of some edge of F. An edge cover F is said to be a minimal edge  
cover if for every edge e ∈ F, F − {e} is not an edge cover. An edge cover with minimum  
cardinality is a minimum edge cover of G. The cardinality of a minimum edge cover is  
called the edge covering number of G and it is denoted by α1(G).  
Remark 2.2. (1) If F is an edge stable set of the graph G with δ(G) ≥ 2 then E − F  
is an edge cover of G. The complement of a maximum edge stable set of G is a minimum  
edge cover of G and vice versa. Therefore,  
α1(G) + αe(G) = |E(G)|.  
n
2
(2) If G is a graph with δ(G) ≥ 2 then any edge cover of G must contain atleast  
edges  
n+1  
2
if n is even and  
edges if n is odd, where n = |V (G)|. Therefore, any edge stable set  
n
n
2
of G contains atmost m −  
edges, where m = |E(G)|. Therefore, αe(G) ≤ m − .  
2
3. Relation between edge H-domination and edge stability  
Definition 3.1. [5] (edge H-dominating set) A set F ⊆ E(G) is said to be an edge H-  
dominating set of G if the following conditions are satisfied by any edge e = uv in E(G).  
42  
B. M. Kakrecha, H. M. Makadia, D. D. Pandya, S. G. Sonchhatra, N. D. Abhangi  
(1) If e is an isolated edge then e ∈ F.  
(2) If e is a pendant edge with v as a pendant vertex and u is not a pendant vertex. If  
uv ∈ F then all the edges incident at u (except e) are in F.  
(3) If e is a pendant edge with u as a pendant vertex and v is not a pendant vertex. If  
uv ∈ F then all the edges incident at v (except e) are in F.  
(4) If neither u nor v is a pendant vertex and uv ∈ F then all the edges incident at u  
(except e) are in F or all the edges incident at v (except e) are in F.  
Example 3.2. Consider the following graph with vertices 1, 2, 3, 4, 5, 6 and edges 12,  
23, 34, 45, 51 and 56.  
Figure 2. Graph G with 6 vertices  
The edge sets {23, 45, 15}, {23, 45, 56} are edge H-dominating sets of the graph given  
in figure 2.  
Theorem 3.3. Let G be a graph with δ(G) ≥ 2. An edge stable set is a maximal edge  
stable set if and only if it is an edge H-dominating set.  
Proof. Suppose that F is an edge stable set and suppose that F is maximal. Let e =  
uv be an edge such that e ∈ F. Since F is maximal F ∪ {e} is not an edge stable set.  
Therefore there is a vertex x such that all the edges incident at x are in F ∪ {e}.  
Suppose that x = u and x = v. Since F is an edge stable set, there is an edge f incident  
at x such that f ∈ F. Therefore f ∈ F ∪ {e} because f = uv. This contradicts the above  
statement that all the edges incident at x are in F ∪ {e}. Thus x = u or x = v. Suppose  
that x = u. Since all the edges incident at x are in F ∪ {e} and e is an edge incident at  
u such that e ∈ F. Therefore all the edges incident at u (except e) are in F. Similarly, if  
x = v then all the edges incident at v (except e) are in F. This proves that F is an edge  
H-dominating set.  
Conversely, suppose that F is an edge stable set which is also an edge H-dominating  
set. To prove that F is maximal. Let e = uv be an edge such that e ∈ F. Suppose that  
all the edges incident at u (except e) are in F then it implies that all the edges incident  
at u are in F ∪ {e}. Similarly, if all the edges incident at v (except e) are in F then all  
the edges incident at v are in F ∪ {e}. This proves that F is maximal.  
□
Definition 3.4. [5] Let G be a graph and F be an edge H-dominating set of G. The set  
F is a minimal edge H-dominating set of G if F − {e} is not an edge H-dominating set  
for every edge e ∈ F.  
EDGE STABLE SETS IN GRAPH  
43  
Theorem 3.5. Let G be a graph with δ(G) ≥ 2. An edge set F is a maximal edge stable  
set of G then F is a minimal edge H-dominating set of G.  
Proof. Let F be a maximal edge stable set of G and e = uv ∈ F. Since F is a maximal  
edge stable set, by theorem 3.3, F is an edge H-dominating set. Now consider F − {uv}  
= F1. Since deg(u) ≥ 2 and deg(v) ≥ 2 also F is an edge stable set of G, there are edges  
f and g incident at u and v respectively (other than uv) such that f ∈ F and g ∈ F.  
Therefore, there is an edge incident at u which is not in F1 and also there is an edge  
incident at v which is not in F1. Thus, F1 is not an edge H-dominating set of G. That  
is, F − {uv} = F1 is not an edge H-dominating set of G. Thus, F is a minimal edge  
H-dominating set of G.  
□
Definition 3.6. [5] An edge H-dominating set with minimum cardinality is a minimum  
edge H-dominating set. The cardinality of a minimum edge H-dominating set is the edge  
H-domination number of G, denoted by γH′ (G).  
Remark 3.7. Let G be a graph and an edge set F is a maximum edge stable set of G.  
The edge stability number αe(G) = |F|. Since F is also a maximal edge stable set of G,  
by theorem 3.5, F is a minimal edge H-dominating set of G. Therefore, γ′ (G) ≤ αe(G).  
H
Example 3.8. Consider the cycle graph C6 with vertices 1, 2, 3, 4, 5, 6.  
Figure 3. Cycle graph C6  
The minimum edge H-dominating sets of C6 are {12, 45}, {23, 56}, {34, 61} also each  
set is maximal edge stable set. But the maximum edge stable sets of C6 are {12, 34, 56},  
{23, 45, 61}. Therefore γ′ (C6) = 2 and αe(C6) = 3. In this example, γ′ (C6) < αe(C6).  
H
H
4. Vertex removal from the graph  
We consider the operation vertex removal from the graph. Let G be a graph with δ(G)  
≥ 3 and a vertex v ∈ V (G).  
Example 4.1. Consider 3-regular graph G with vertices 1, 2, 3, 4, 5, 6 and edges 12, 23,  
34, 45, 56, 61, 14, 25 and 36.  
The edge set F1 = {25, 36, 34} is a maximal edge stable set of G − 1, however F1  
is not a maximal edge stable set of G because by theorem 3.3, F1 is not an edge H-  
dominating set of G. Also it is observed from the graph of figure 4 that the edge set F =  
{14, 12, 25, 36, 34, 56} is a larger edge stable set of G containing F1.  
44  
B. M. Kakrecha, H. M. Makadia, D. D. Pandya, S. G. Sonchhatra, N. D. Abhangi  
Figure 4. 3-regular graph G with 6 vertices  
Proposition 4.2. If F ⊆ E(G) is an edge stable set of G − v then F is also an edge  
stable set of G.  
Proof. Let x be any vertex of G. If x = v then x is a vertex of G − v and therefore there  
is an edge e incident at x such that e ∈ F. If x = v then any edge incident at v is not in  
F. Therefore F is an edge stable set of G.  
□
Proposition 4.3. Let G be a graph and a vertex v ∈ V (G) then αe(G − v) ≤ αe(G).  
Proof. Let F be a maximum edge stable set of G − v then by proposition 4.2, F is also  
an edge stable set of G. Therefore αe(G − v) = |F| ≤ αe(G).  
□
5. Edge removal from the graph  
We consider the graph G with δ(G) ≥ 3.  
Proposition 5.1. Let G be a graph with δ(G) ≥ 3 and M is a maximal edge stable set  
of G. For e = uv ∈ M, M − {e} is a maximal edge stable set of G − e.  
Proof. It is obvious that M − {e} is an edge stable set of G − e. To prove that M − e  
is maximal, let xy be any edge of G − e. If x, y ∈ {u, v} then since M is a maximal edge  
stable set of G, all the edges incident at x are in M or all the edges incident at y are in  
M. These edges are the edges of G − e. Therefore, all the edges incident at x are in M  
− e or all the edges incident at y are in M − e.  
Suppose that x = u and y = v. Now uy is an edge of G which is not in M. Since M  
is maximal, all the edges incident at u are in M or all the edges incident at y are in M.  
Since the edge e = uv is not in M − {e}. It follows that all the edges of G − e incident  
at u are in M − {e} or all the edges incident at y are in M − {e}. Therefore, M − {e}  
is a maximal edge stable set of G − e.  
□
Theorem 5.2. Let e = uv be any edge of G then αe(G − e) < αe(G).  
Proof. Let M be any maximum edge stable set of G − e. There is an edge h incident at  
u and there is an edge h′ incident at v such that h, h′ ∈ M. Let M 1 = M ∪ {e} then  
obviously, M 1 is an edge stable set of G. Therefore, αe(G) ≥ |M 1| > |M | = αe(G −  
e).  
□
EDGE STABLE SETS IN GRAPH  
45  
Theorem 5.3. Let e = uv be any edge of G then αe(G − e) = αe(G) − 1 if and only if  
there is a maximum edge stable set M of G such that e ∈ M.  
Proof. Suppose that αe(G − e) = αe(G) − 1. Let M 1 be a maximum edge stable set of  
G − e and let M = M 1 ∪ {e}. Since αe(G − e) = αe(G) − 1, M is a maximum edge  
stable set of G and e ∈ M.  
Conversely, suppose that there is a maximum edge stable set M of G such that e ∈ M.  
Let M 1 = M − {e} then M 1 is a maximum edge stable set of G − e. Therefore, αe(G −  
e) = |M 1| = |M | − 1 = αe(G) − 1.  
□
6. Maximal edge stable set with minimum cardinality  
Definition 6.1. A maximal edge stable set with minimum cardinality is called an I′ -set.  
The cardinality of I′ -set is denoted by I′ (G).  
Theorem 6.2. Let G be a graph with δ(G) ≥ 3 and e = uv be any edge of G then I′ (G  
− e) < I′ (G) if and only if there is an I′ − set M of G such that e ∈ M.  
Proof. Suppose that there is an I′ − set M of G such that e ∈ M. Let M 1 = M − {e}  
then by proposition 5.1, M 1 is a maximal edge stable set of G − e. Therefore, I′ (G − e)  
≤ |M1| < |M| = I′ (G).  
Conversely, suppose that I′ (G − e) < I′ (G). Let M 1 be an I′ − set of G − e. Let N =  
M 1 ∪ {e} then N is a maximal edge stable set of G. Since I′ (G − e) < I′ (G), N is an  
I′ − set of G. Obviously, e ∈ N.  
□
Corollary 6.3. Let G be a graph with δ(G) ≥ 3. If I′ (G − e) < I′ (G) then I′ (G − e)  
= I′ (G) − 1.  
Remark 6.4. Let G be a graph with δ(G) ≥ 2 then By remark 2.2(2) and remark 3.7,  
we have the following inequality chain.  
γ′ (G) ≤ I′ (G) ≤ αe(G) ≤ m −  
n
2
H
γ′ (G) ≤ I′ (G) ≤ αe(G) ≤ Γ′ (G)  
H
H
7. Concluding remarks and further scope  
The edge stability in graph is a new edge variant and hereditary property which rep-  
resents a particular edge set of the graph. In this paper, it is proved that a vertex (or  
an edge) removal operation may decrease (does not increase) the edge stability number  
of the graph. How many units the number decreases is the further scope of investigation.  
The relation between edge H-domination number and edge stability number is written as  
an inequality chain. This chain can be improved further with other edge parameters like  
edge domination number, edge independence number, edge covering number etc. of the  
graph.  
46  
B. M. Kakrecha, H. M. Makadia, D. D. Pandya, S. G. Sonchhatra, N. D. Abhangi  
REFERENCES  
[1] Acharya, B. D., Domination in hypergraphs, AKCE J. Graphs. Combin., 4(2), pp. 117-126, (2007).  
[2] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., Domination in Graphs Advanced Topics, Marcel Dekker,  
Inc., New York (1998).  
[3] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., Fundamental of Domination in Graphs, Marcel Dekker,  
Inc., New York (1998).  
[4] Kakrecha, B. M., Ph. D. Thesis, Saurashtra University, Rajkot (2017).  
[5] Kakrecha, B. M., Edge H-domination in Graph, TWMS Journal of Applied and Engineering Mathematics,  
11(2), pp. 448-458, (2021).  
[6] Kakrecha B. M., Weak Edge Domination in Graph, Advances and Applications in Mathematical Sciences,  
Mili Publications, 23(1), pp. 61-75, (2023).  
[7] Thakkar D. K. and Kakrecha B. M., Vertex Removal and the Edge Domination Number of Graphs, Interna-  
tional Journal of Mathematics And its Applications, 4(2A), pp. 1-5, (2016).  
[8] Thakkar D. K. and Kakrecha B. M., About the Edge Covers of the Graph, International Journal of Scientific  
and Innovative Mathematical Research, 5(1), pp. 1-7, (2017).  
(Received, September 1, 2024)  
(Revised, July 14, 2025)  
12345Department of Mathematics,  
Government Engineering College,  
Movdi-Kankot Road, Rajkot-360005,  
Gujarat, INDIA.  
Email1: kakrecha.bhavesh2011@gmail.com  
Email2: hmmakadia@gecrajkot.ac.in  
Email3: drddp.gec@gmail.com  
Email4: sonchhabda.sunil20@gmail.com  
Email5: nikhil.abhangi@gmail.com