Electronic Journal of Graph Theory and Applications 12 .
, 273Ae288 1-well-covered graphs containing a clique of size n/3 Zakir Deniz Department of Mathematics.
DuOzce University.
DuOzce, 81620.
Turkey.
zakirdeniz@duzce.
Abstract A graph is well-covered if all of its maximal independent sets have the same size.
A graph that remains well-covered upon the removal of any vertex is called a 1-well-covered graph.
These graphs, when they have no isolated vertices, are also known as W2 graphs.
It is well-known that every graph G OO W2 has two disjoint maximum independent sets.
In this paper, we investigate connected W2 graphs with n vertices that contain a clique of size n/3.
We prove that if the removal of two disjoint maximum independent sets from a graph G OO W2 leaves a clique of size at least 3, then G contains a clique of size n/3.
Using this result, we provide a complete characterization of these graphs, based on eleven graph families.
Keywords: independent set, clique, matching, well-covered Mathematics Subject Classification : 05C69,05C70, 05C99 DOI: 10.
5614/ejgta.
Introduction We consider only simple, finite, and undirected graphs, and use standard terminology.
A set of vertices in a graph is called independent if none of its vertices share an edge.
An independent set that has the largest possible size is referred to as a maximum independent set.
The number of vertices in the largest independent set of a graph G is known as the independence number, denoted by (G).
The problem of identifying graphs where every maximal independent set is also a maximum independent set was introduced by M.
Plummer in 1970, who referred to such Received: 17 February 2022.
Revised: 18 August 2024.
Accepted: 23 August 2024.
1-well-covered graphs containing a clique of size n/3 Deniz graphs as well-covered.
Since then, numerous studies have been conducted on this topic.
Identifying well-covered graphs is generally a co-NP-complete problem .
, .
However, certain subclasses of well-covered graphs can be recognized in polynomial time .
, 8, 3, .
Staples introduced W2 graphs in 1979 as graphs in which any two disjoint independent sets are contained within two disjoint maximum independent sets .
These graphs are also referred to as 1-well-covered graphs without isolated vertices, meaning they remain well-covered even after the removal of any vertex.
Hence, a graph G belongs to W2 if and only if G is 1-well-covered without isolated vertices .
After the initial exploration of fundamental properties of 1-well-covered graphs in .
, various studies focused on specific subclasses.
Pinter characterized two categories of planar 1-well-covered graphs: those that are 4-regular and 3connected .
, and those with girth 4 .
He also developed constructions for infinite families of 1-well-covered graphs with girth 4 .
Subsequently.
Hartnell provided a characterization of 1-well-covered graphs without 4-cycles in .
Hoang and Trung .
gave a characterization of the W2 graphs satisfying the condition that every triangle is also a dominating set for the graph.
Recently.
Deniz and Ekim investigated edge stable equimatchable graphs which actually coincide 1-well-covered line graphs .
Also.
Levit and Mandrescu gave some characterizations of 1-well-covered graphs in terms of the existence of special independent sets .
More recently.
Deniz .
gave a detailed study on a classification of 1-well-covered graphs with respect to their independence and matching numbers.
A vertex x of a graph G is called shedding if for every independent set S in GOeNG .
, there is a vertex v OO NG .
so that S O .
is independent.
W2 graphs are also known as graphs in which every vertex is a shedding vertex.
In fact.
Levit and Mandrescu showed in .
that for a vertex v in a well-covered graph G without isolated vertices G Oe v is well-covered if and only if v is shedding.
Shedding vertices are closely connected to independence complexes of graphs in combinatorial topology.
Specifically, they are crucial in determining vertex-decomposable graphs, as there must be an ordering of shedding vertices in a graph G to classify it as vertexdecomposable .
, .
In this paper, we study 1-well-covered graphs with n vertices that contain a clique of size n/3.
Note that every graph G OO W2 , where W2 is the class of 1-well-covered graph without isolated vertices, has two disjoint maximum independent sets.
We show that for a graph G OO W2 if G Oe (I1 O I2 ) is a clique of size t for disjoint maximum independent sets I1 and I2 , then G has at most 3t vertices.
Theorem 1.
Let G OO W2 with n vertices, and suppose that I1 and I2 are disjoint maximum independent sets.
If S = V (G)Oe(I1 OI2 ) induces a clique of size at least 3 in G, then n O .
S|.
Notice that if G is a graph as described in Theorem 1.
1, then G has at most .
S| vertices.
Since G has two disjoint maximum independent sets, we have (G) O |S|.
This implies that G has a clique of size at least n/3.
Hence, for a connected graph G OO W2 , if S = V (G)Oe(I1 OI2 ) induces a clique of size at least 3 for a pair of disjoint maximum independent sets I1 and I2 , then G has a clique of size at least n/3.
For a given graph in W2 , we show how to construct an infinite family of W2 graphs.
then divide categorize the graphs for which G Oe (I1 O I2 ) is a clique for disjoint maximum independent sets I1 and I2 , into three subclasses with respect to their independence numbers.
1-well-covered graphs containing a clique of size n/3 Deniz These results allow us to achieve a complete characterization of such graphs, presented as a list of eleven graph families.
Theorem 1.
A connected graph G is in W2 such that the removal of two disjoint maximum independent sets from G leaves a clique if and only if G belongs to one of the graph classes C(G2 ).
C(G3 ), .
C(G9 ).
C(K2 ).
C(C5 ) and C(Kt K2 ) for t Ou 2 .
ee Figures 3 and .
The remainder of this paper is organized as follows.
In Section 2, we begin with definitions and preliminary results related to 1-well-covered graphs.
In Section 3, we introduce the graph G.
for a given 1-well-covered graph G and a vertex u OO V (G).
Finally, in Section 4, we consider the graph G belonging to W2 for which S = G Oe (I1 O I2 ) induces a clique in G, where I1 and I2 are two disjoint maximum independent sets.
Preliminaries Let G = (V.
E) be graph and given a subset of vertices S, the subgraph induced by S in G is denoted by G[S], and G \ S represents the subgraph induced by V \ S, i.
G[V \ S].
When S consists of a single vertex v, we denote G \ S by G Oe v.
The graph G Oe S thus corresponds to the subgraph G[V (G) Oe S].
For a vertex v, the open neighborhood of v in a subgraph H is denoted by NH .
, and the closed neighborhood of v, denoted by NH .
, is NH .
O v.
If the subgraph H is clear from context, the subscript H is omitted.
For a subset S OI V .
NH (S) .
NH [S]) represents the union of the open .
neighborhoods of the vertices in S.
say that S is complete to T for S.
T OC V (G) if every vertex in S is adjacent to all vertices in T .
Additionally, we use the notation .
to refer the set 1, 2, .
, k.
We use the notation Kn .
Cn , and Pn to represent the complete graph, cycle, and path on n vertices, respectively.
Additionally.
Kr,s denotes the complete bipartite graph for any r, s Ou 1.
The notation rK2 refers to a graph consisting of r components, each being K2 .
A graph G is said to be F -free if none of its induced subgraphs is isomorphic to F .
The notations dG .
OI(G), and (G) represent the degree of a vertex x, the maximum and minimum degrees of a graph G, respectively.
A vertex with degree one is called leaf, while a vertex with degree zero is called leaf.
A subgraph of G that is isomorphic to a complete graph is referred to as a clique.
The clique number of a graph G, denoted by O(G), represents the number of vertices in the largest clique in G.
A matching is a collection of edges in G such that no two edges share a common endpoint.
The maximum size of a matching in G is known as the matching number of G, denoted by AA(G).
A matching M saturates a vertex v if v is an endpoint of an edge in M .
otherwise, the vertex v is considered unsaturated by M .
A vertex u in a graph G is said to be dominated by another vertex v OO V (G) \ u if NG .
OI NG .
A subset S OI V (G) dominates a set of vertices T if every vertex in T is adjacent to at least one vertex in S.
Recall that each graph in W2 has two disjoint maximum independent sets.
For simplicity, we will refer to these as DMI sets.
We begin by stating some established results related to well-covered graphs, which will be used in the remainder of the paper.
Theorem 2.
Let S be an independent set in a graph G.
Then, every independent set disjoint from S can be matched into S if and only if S is maximum.
1-well-covered graphs containing a clique of size n/3 Deniz Theorem 2.
Let G be a well-covered graph and let v be a non-isolated vertex.
Then v is a shedding vertex.
if and only if G Oe v is well-covered.
It directly follows from Theorem 2.
2 that every vertex in a graph G OO W2 is a shedding Theorem 2.
The graph G OO W2 if and only if (G Oe .
= (G) and G Oe v is wellcovered, for every v OO V (G).
Theorem 2.
3 shows that W2 graphs and 1-well-covered graphs are equivalent when the graph has no isolated vertices.
Therefore, 1-well-covered graphs without isolated vertices are the same as W2 graphs.
Additionally, when the graph is connected, these two graph families Hence, we typically use the W2 notation instead of referring to connected 1-wellcovered graphs.
Recall that while every vertex of a graph in W2 is a shedding vertex, the converse is not that is, a graph where each vertex is a shedding vertex does not necessarily belong to W2 .
Indeed, the graph H1 in Figure 1 has the property that each of its vertices is a shedding vertex, yet H1 is not in W2 .
Consider the other graphs in Figure 1.
The graph H2 is a well-covered but does not belong to W2 .
The graph H3 belongs to W2 and is also well-covered.
Finally, the graph H4 is neither well-covered nor a member of W2 .
Figure 1: The graphs H1 .
H2 .
H3 , and H4 .
Proposition 2.
If G is a connected graph in W2 with n vertices such that (G) AA(G) = n, then G is isomorphic to K2 .
The only connected bipartite graph belonging to W2 is K2 .
Lemma 2.
Let G be a graph in W2 .
Then, the graph G Oe NG [S] is in W2 for every independent set S in G.
In particular, (G) = (G Oe NG [S]) |S|.
We note that if v is a shedding vertex in a graph G, then it follows from the definition of shedding vertex that there is no independent set S in G Oe NG .
that dominates NG .
This, in particular, implies that G does not have any dominated vertices.
Corollary 2.
If G is a connected graph with at least 3 vertices, then no shedding vertex in G can be a leaf vertex.
In particular, when G OO W2 , it follows that (G) Ou 2.
1-well-covered graphs containing a clique of size n/3 Deniz According to .
Corollary 2.
, the only connected graphs in W2 with order 2(G) 1 are C3 and C5 .
From this, the following observation can be made.
Corollary 2.
Let G OO W2 .
Then G Oe x is a bipartite well-covered graph for some x OO V (G) if and only if G is C3 or C5 .
By definition, a graph G belongs to W2 if any two disjoint independent sets in G can be extended to two DMI sets.
Thus, in a graph G OO W2 , every pair of disjoint independent sets can be expanded to form two DMI sets.
We often use this property of W2 in order to show that a graph belongs to the class W2 .
Insertion and deletion of vertices in 1-well-covered graphs In a 1-well-covered graph, by definition, the removal of any vertex does not change its wellcoveredness property while it may not to be 1-well-covered.
In this section, we investigate these graphs of when it is possible to add .
r delet.
a vertex in the graph under preserving its 1-well-covered property.
Definition 3.
Any two vertices u, v in a graph G are said to be twins if u and v have the same set of neighbours, that is, if NG .
= NG .
We make a slight modification to this definition as follows.
a pair u, v in G is called a c-twin if NG .
= NG .
Given a connected graph G and a vertex u OO V (G).
We define the graph G.
: .
as a graph obtained from G by adding a new vertex w to G and make adjacent w with all vertices of NG .
Namely.
V (G.
: .
) = V (G) O .
and E(G.
: .
) = E(G) O .
v : v OO NG .
Observe that u and w are c-twin vertices in the graph G.
: .
For instance, if G = C5 , and u is any vertex in G, then G.
: .
is the graph depicted in Figure 2.
Figure 2: The graph G.
: .
It can be easily observed that (G) = (G.
: .
) for every graph G and u OO V (G).
next show that G.
: .
preserves its 1-well-covered property.
Theorem 3.
Let G OO W2 and u OO V (G).
Then G.
: .
is in W2 as well.
Proof.
We pick two disjoint independent sets T1 .
T2 in G.
: .
, and we extend them to two DMI sets in G.
: .
so that G.
: .
belongs to W2 .
First, if w OO / T1 O T2 , then there exist two DMI sets in G.
: .
containing T1 and T2 , since G OO W2 .
Therefore, we further assume that w OO T1 O T1 .
Note that w cannot be in both T1 1-well-covered graphs containing a clique of size n/3 Deniz and T2 , since they are disjoint.
Assume without loss of generality that w OO T1 .
Notice that NG .
= NG.
Oe w, and T1 O NG .
= .
Let u OO T2 .
Obviously T2 O NG .
= .
By Lemma 2.
G Oe NG .
is in W2 , which implies that there exist two DMI sets S1 .
S2 in G Oe NG .
containing T1 Oe w and T2 Oe u.
Then the sets S1 O .
and S2 O .
are two DMI sets in G.
: .
containing T1 and T2 , respectively, as claimed.
Let u OO / T2 .
Consider the sets (T1 Oe .
O .
and T2 , they are clearly disjoint.
Since G OO W2 , we can extend (T1 Oe .
O .
and T2 to two DMI sets S1 and S2 in G, respectively.
Thus, the sets S A = (S1 Oe .
O .
and S2 are DMI sets in G.
: .
containing T1 and T2 , respectively, as claimed.
Hence.
G is in W2 .
Corollary 3.
If G is well-covered, and u OO V (G), then G.
: .
is well-covered as well.
In a well-covered graph G, a vertex w OO V (G) is said to be extendable if G Oe w is wellcovered and (G) = (G Oe .
Extendable vertices were used in .
, .
in order to construct some families of well-covered graphs.
Following Theorem 3.
1, it turns out that the vertices u and w in the graph G.
: .
are Corollary 3.
If G is a well-covered graph and u OO V (G), then u and w are extendable vertices in the graph G.
: .
The converse of Theorem 3.
1 is not generally true since the graph G1 Oe w for a vertex w of degree 2 is not 1-well-covered although G1 OO W2 .
ee Figure .
Figure 3: The graphs G1 .
G2 , .
G5 .
1-well-covered graphs containing a clique of size n/3 A graph G belonging to W2 can be partitioned into three sets I1 .
I2 .
S where I1 and I2 are two disjoint independent sets in G, and S = V (G) Oe (I1 O I2 ).
In this section, we first bound the size of G by .
S| when G Oe (I1 O I2 ) is a clique for DMI sets I1 and I2 .
By using this result, we further obtain a complete characterization of those graphs.
Notice that a graph G is in W2 if and only if every connected component of G is in W2 .
Therefore, we will focus exclusively on connected graphs in W2 for the remainder of the paper.
1-well-covered graphs containing a clique of size n/3 Deniz Proposition 4.
Let G OO W2 , and suppose that I1 and I2 are DMI sets.
If S = V (G)Oe(I1 OI2 ) induces a clique in G, then every vertex in S has exactly one neighbour in each of I1 .
I2 .
Proof.
Suppose that S = V (G) Oe (I1 O I2 ) induces a clique in G for DMI sets I1 and I2 with |Ii | = r for i = 1, 2.
Since G is well-covered, every vertex in S has a neighbour in each of I1 .
I2 .
Indeed, if there exists u OO S having no neighbour in I1 , then I1 O .
would be a maximal independent set of size r 1, a contradiction.
Let u OO S be given.
By Lemma 2.
G Oe NG .
is in W2 with (G Oe NG .
) = r Oe 1.
Note that the graph G Oe NG .
is bipartite since S induces a clique in G.
Then, by Proposition 2.
that G Oe NG .
is isomorphic to .
Oe .
K2 .
Then, we conclude that any vertex u OO S cannot have more than one neighbour in Ii for i OO .
, .
since otherwise the graph G Oe NG .
would have at most 2r Oe 3 vertices, a contradiction.
Consequently, every vertex in S has exactly one neighbour in each of I1 .
I2 .
Proposition 4.
Let G OO W2 .
Suppose S = V (G)Oe(I1 OI2 ) for DMI sets I1 = .
1 , x2 .
, xr } and I2 = .
1 , y2 .
, yr } with .
1 y1 , x2 y2 , .
, xr yr } OC E(G).
Then, for each i OO .
, at least one endpoint of the edge xi yi is adjacent to a vertex in S.
Proof.
Assume for a contradiction that there exists an index i OO .
such that NG (S)O.
i , yi } = OI.
We then deduce that NG .
i ) OI I2 and NG .
i ) OI I1 .
Recall also that, by Corollary 2.
1, the minimum degree of a graph belonging to W2 is at least 2, so |NG .
i ) O I1 | Ou 2.
Therefore.
NG .
i ) is dominated by I1 Oe xi .
Nevertheless, this gives a contradiction since xi is a shedding Notice that if G is in W2 with n vertices such that G Oe (I1 O I2 ) is a clique for DMI sets I1 and I2 , then G contains a clique of size n Oe 2(G).
Next let us show that G cannot contain a clique of size n Oe 2(G) 2 when G = Kn for n OO N.
Proposition 4.
Let G OO W2 with n vertices, and G = Kn .
For DMI sets I1 and I2 , if S = V (G) Oe (I1 O I2 ) induces a clique in G, then |S| O O(G) O |S| 1.
Proof.
Suppose that S = V (G) Oe (I1 O I2 ) induces a clique in G for DMI sets I1 and I2 .
Then.
G contains a clique of size n Oe 2(G) = |S|, so O(G) Ou |S|.
Let (G) = r.
I1 = .
1 , x2 .
, xr } and I2 = .
1 , y2 .
, yr }.
We may assume .
1 y1 , x2 y2 , , xr yr } OC E(G) by Theorem 2.
Clearly r Ou 2 since G = Kn .
Assume for a contradiction that there exist xi OO I1 and yj OO I2 such that .
i , yj } is complete to S.
Then i = j by Proposition 4.
2 together with Proposition 4.
This means that xi has at least two neighbours in I2 , which are yi , yj OO I2 .
Also.
G Oe NG .
i ] is bipartite since xi is complete to S.
Then, by Proposition 2.
1 that G Oe NG .
i ] is isomorphic to .
Oe .
K2 .
However.
G Oe NG .
i ] has at most 2r Oe 3 vertices since xi has at least two neighbours in I2 , a contradiction.
Thus, there are no such xi OO I1 and yj OO I2 .
Hence.
G has no clique of size n Oe 2(G) 2.
Consequently, |S| O O(G) O |S| 1.
We next state some technical results related to W2 graphs with the partition I1 .
I2 and S.
Proposition 4.
Let G OO W2 .
Suppose that G Oe (I1 O I2 ) is a clique for DMI sets I1 and I2 .
Then every vertex in I1 .
I2 ) has at most two neighbours in I2 .
I1 ).
1-well-covered graphs containing a clique of size n/3 Deniz Proof.
We assume to the contrary that there exists x OO I1 such that it has at least three neighbours in I2 .
Then (G Oe NG .
) = (G) Oe 1 and |I2 Oe NG .
| O (G) Oe 3.
However, we cannot extend the independent sets I1 Oe x and (I2 Oe NG .
) O .
into two DMI sets in G as G Oe (I1 O I2 ) is a clique, a contradiction that G OO W2 .
By symmetry, the claim follows when a vertex y of I2 has more than two neighbours in I1 .
Lemma 4.
Let G OO W2 .
Suppose that for DMI sets I1 and I2 , the set S = V (G) Oe (I1 O I2 ) induces a clique of size at least 3 in G.
If (G) Ou 4, then every vertex in I1 O I2 has a neighbour in S.
Proof.
Suppose that S = V (G) Oe (I1 O I2 ) induces a clique of size |S| Ou 3 in G for DMI sets I1 and I2 .
Let (G) = r Ou 4.
I1 = .
1 , x2 .
, xr } and I2 = .
1 , y2 .
, yr }.
Clearly.
G has n = 2r |S| vertices.
By Theorem 2.
1, we may assume .
1 y1 , x2 y2 , .
, xr yr } OC E(G).
Assume for a contradiction that there exists xi OO I1 for i OO .
such that it has no neighbour in S.
By Corollary 2.
1 and Proposition 4.
4, xi has exactly two neighbours in I2 .
Then, we claim that every vertex in S is adjacent to one of the neighbours of xi in I2 .
Indeed, if u OO S is adjacent to none of the neighbours of xi in I2 , then xi and its two neighbours would survive in GOeNG .
However.
GOeNG .
must consist of K2 components by Proposition 2.
1 and Lemma 1, a contradiction.
Thus, by Proposition 4.
1, there exists yj OO I2 having no neighbours in S due to r Ou 4.
Clearly, we have i = j by Proposition 4.
Similarly as before, yj has exactly two neighbours in I1 , also every vertex in S is adjacent to one of the two neighbours of yj in I1 .
Since for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2 by Proposition 4.
1 and r Ou 4, we deduce that |NG (S) O It | = 2.
It then follows from Proposition 2 that we have (G) = r = 4, and exactly one endpoint of each edge xEe yEe has a neighbour in S for Ee OO .
We may then assume without loss of generality that NG .
i ) = .
3 , y4 }.
NG .
j ) = .
1 , x2 }, and let i = 4, j = 1.
Let u, v OO S such that u OO NG .
1 ) and v OO N .
2 ).
Obviously, x1 .
x2 ) is the unique neighbour of u .
in I1 by Proposition 4.
Notice also that the graph G Oe NG .
is in W2 by Lemma 2.
1, and so G Oe NG .
consists of K2 components by Proposition 2.
However, x2 and its two neighbours y1 , y2 belong to G Oe NG .
, a contradiction.
Result 4.
Let G OO W2 .
Suppose that for DMI sets I1 and I2 , the set S = V (G) Oe (I1 O I2 ) induces a clique of size at least 3 in G.
If (G) Ou 4, then (G) O |S|.
Proof.
By Lemma 4.
1, every vertex in I1 O I2 has a neighbour in S.
Moreover, each vertex of S has exactly one neighbour in Ii for i = 1, 2 by Proposition 4.
Thus, we conclude that (G) O |S| as claimed.
Let us now prove one of our main results, which will be essential for the proof of Theorem Theorem 1.
Let G OO W2 with n vertices, and suppose that I1 and I2 are DMI sets.
S = V (G) Oe (I1 O I2 ) induces a clique of size at least 3 in G, then n O .
S|.
Proof.
Suppose that I1 .
I2 are DMI sets in G, and let S = V (G) Oe (I1 O I2 ) induce a clique of size at least 3 in G.
By Result 4.
1, if (G) Ou 4, then (G) O |S|.
It then follows that n O .
S| since G has n = 2r |S| vertices.
Also, if (G) O 3, then n O .
S| since |S| Ou 3 Ou r.
1-well-covered graphs containing a clique of size n/3 Deniz Given two graphs H1 and H2 .
The corona H1 H2 is the graph obtained by taking each vertex of H1 and connecting it to all vertices of a copy of H2 .
ee, for instance.
Figure .
Clearly, the graph G1 in Figure 3 corresponds to the graph K2 K2 .
Figure 4: .
The graph P3 K1 .
The graph K3 K2 .
The provided upper bound in Theorem 1.
1 is sharp since the graph Kt K2 attains the bound for each t Ou 3.
We next state an easy consequence of Theorem 1.
Corollary 4.
Let G OO W2 with n vertices.
For DMI sets I1 and I2 , if G Oe (I1 O I2 ) is a clique of size at least 3, then (G) O n3 O O(G).
Proposition 4.
Suppose that G OO W2 with n vertices.
For DMI sets I1 and I2 , if G Oe (I1 O I2 ) is isomorphic to K2 , then (G) O 3.
Proof.
Suppose that S = V (G) Oe (I1 O I2 ) induces a K2 in G for DMI sets I1 and I2 .
Assume for a contradiction that (G) Ou 4.
By Propositions 4.
1 and 4.
2, we deduce that (G) = 4.
Then G has |S| 8 = 10 vertices.
Let I1 = .
1 , x2 , x3 , x4 }.
I2 = .
1 , y2 , y3 , y4 }, and S = .
, .
By Theorem 2.
1, we may assume .
1 y1 , x2 y2 , x3 y3 , x4 y4 } OC E(G).
Recall that for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2 by Proposition 4.
1, also for each i OO .
, at least one endpoint of the edge xi yi is adjacent to S by Proposition 4.
Thus, we deduce that S has exactly two neighbours in each of I1 .
I2 , and so the remaining two vertices of each I1 .
I2 have no neighbour in S.
Without loss of generality, we may assume that NG (S) = .
1 , x2 , y3 , y4 }, and NG .
O I2 = .
3 }.
By Corollary 2.
1 and Proposition 4.
4, x3 has exactly two neighbours in I2 .
Then, by applying the same process as in the proof of Lemma 4.
1, we claim that every vertex in S is adjacent to one of the two neighbours of x3 in I2 .
Indeed, if there exists u OO S having no neighbour in NG .
3 ), then x3 and its two neighbours would survive in G Oe NG .
However.
G Oe NG .
must consist of K2 components by Lemma 2.
1 and Proposition 2.
1, a This forces that NG .
3 ) = .
3 , y4 }.
By the same reason, every vertex in S is adjacent to one of two neighbours of x4 in I2 .
Therefore NG .
3 ) = .
3 , y4 } = NG .
4 ).
On the other hand, the graph G Oe NG .
is in W2 by Lemma 2.
1, and so G Oe NG .
consists of K2 components by Proposition 2.
However, y4 and its two neighbours x3 , x4 belong to G Oe NG .
, a contradiction.
For a connected graph G OO W2 with n vertices, suppose that G Oe (I1 O I2 ) is a clique of size t for DMI sets I1 and I2 .
If t Ou 3, then, by Corollary 4.
G has at most n3 vertices.
On the other hand, if t O 2, then G has at most 3t 2 vertices by Corollary 2.
2 and Proposition 4.
1-well-covered graphs containing a clique of size n/3 Deniz Corollary 4.
Let G OO W2 with n vertices.
For DMI sets I1 and I2 , if G Oe (I1 O I2 ) is a clique of size t with t O 2, then n O 3t 2 O 8, and O(G) Ou nOe2 By combining Corollaries 4.
1 and 4.
2, we obtain the following.
Result 4.
Let G OO W2 with n vertices.
If the removing of two DMI sets from G leaves a clique, then G has a clique of size nOe2 We now consider the W2 graphs obtained from another one by attaching some c-twin vertices.
Actually, we have already shown in Theorem 3.
1 that if G OO W2 and u OO V (G), then G.
: .
is in W2 as well.
We now consider the case of adding more than one c-twin consecutively.
Given a connected graph H OO W2 such that S = V (H) Oe (I1 O I2 ) induces a clique in H for DMI sets I1 and I2 .
We define a graph family C(H) whose members consist of the graph obtained from H by adding a vertex set T into S and making all vertices of T as c-twin with some vertices of S so that T O S induces a clique in the resulting graph.
In other words, a graph G belongs to C(H) if there exists a set of c-twin vertices T OC S such that G Oe T is isomorphic to H where S = V (G) Oe (I1 O I2 ) induces a clique in G for DMI sets I1 and I2 .
Clearly.
H OO C(H).
For instance, if H = C3 , then C(C3 ) = C(K1 K2 ) consists of complete graphs having at least three vertices.
Also, a member of C(K3 K2 ) is depicted in Figure 5 where the vertices u, v are added into the graph K3 K2 .
Figure 5: A member of C(K3 K2 ).
For a given connected graph H OO W2 , all the members of C(H) are in W2 by Theorem 3.
Proposition 4.
Let H OO W2 such that S = V (H) Oe (I1 O I2 ) induces a clique in H for DMI sets I1 and I2 .
Then every member of the graph family C(H) is in W2 .
In the rest of the paper, we shall give our main result (Theorem 1.
via a series of lemmas where we split the proof into three cases with respect to (G).
Lemma 4.
Let G OO W2 .
Suppose that for DMI sets I1 and I2 , the subgraph G Oe (I1 O I2 ) is a clique.
If (G) = r Ou 4, then G belongs to C(Kr K2 ).
Proof.
Let (G) = r Ou 4.
Then |S| = t Ou 3 by Proposition 4.
5, and we have |S| Ou (G) Ou 4 by Result 4.
It follows from Theorem 1.
1 that n O .
S| = 3t.
Let I1 = .
1 , x2 .
, xr }.
I2 = .
1 , y2 .
, yr }, and S = .
1 , u2 , .
, ut } with t Ou r Ou 4.
By Theorem 2.
1, we may assume .
1 y1 , x2 y2 , .
, xr yr } OC E(G).
Notice that, for each ui OO S, 1-well-covered graphs containing a clique of size n/3 Deniz the graph G Oe NG .
i ] consists of K2 components by Proposition 2.
1 and Lemma 2.
1, since S OC NG .
i ].
We first show that G[I1 O I2 ] is isomorphic to rK2 .
Assume by contradiction that xi is adjacent to yj for some i, j OO .
with i = j.
Recall that each vertex of I1 O I2 has a neighbour in S by Lemma 4.
Moreover, for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2 by Proposition 4.
Consider a vertex yk OO I2 for k OO .
with k OO / .
, .
, there exists u OO S O NG .
k ).
Since u has a unique neighbour in I2 , the vertex u has to be adjacent to xi , since otherwise xi and its two neighbours yi , yj would survive in G Oe NG .
, contradicting that G Oe NG .
consists of K2 components.
Clearly.
G Oe NG .
= G[I1 O I2 ] Oe .
i , yk }.
then deduce that G[I1 O I2 ] Oe .
i , yk } is isomorphic to .
Oe .
K2 , and so xk yi OO E(G).
Let us next consider the vertex yj OO I2 .
By assumption, there exists v OO S O NG .
j ).
Then, similarly as before, v has to be adjacent to xk , since otherwise xk and its two neighbours yi , yk would survive in G Oe NG .
, a contradiction with the fact that G Oe NG .
consists of K2 components.
This again implies that G[I1 O I2 ] Oe .
k , yj } is isomorphic to .
Oe .
K2 , and so xj yk OO E(G).
Finally, let us take the vertex xj OO I1 , and we apply the same process as before.
By assumption there exists w OO S O NG .
j ), and thus w has to be adjacent to yi , since otherwise yi and its two neighbours xi , xk would survive in G Oe NG .
, contradicting that G Oe NG .
consists of K2 This again implies that G[I1 O I2 ] Oe .
j , yi } is isomorphic to .
Oe .
K2 .
Since r Ou 4, there exists xEe OO I1 for Ee OO .
\ .
, j, .
, also we have z OO S O NG .
Ee ) by Lemma It follows that z has to be adjacent to all .
i , yj , yk }, since otherwise yi .
r yj , yk ) and its two neighbours would survive in G Oe NG .
, contradicting that G Oe NG .
consists of K2 However, z can not have more than one neighbour in I2 by Proposition 4.
1, a We therefore conclude that xi is not adjacent to yj .
So.
G[I1 O I2 ] is isomorphic to rK2 .
Observe that if a vertex u OO S is adjacent to xi , yj with i = j, then the edge xj yi must appear in G since G Oe NG .
consists of K2 components.
However, this is not possible because G[I1 O I2 ] is isomorphic to rK2 by above claim.
We therefore infer that each vertex of S is adjacent to only both endpoints of an edge xi yi in G[I1 O I2 ] for i OO .
It follows that there exists S A OC S with |S A | = r such that G[I1 O I2 O S A ] is isomorphic to Kr K2 .
On the other hand, if S has more than r vertices, then some vertices of S have the same neighbours in I1 O I2 , since each vertex of S is adjacent to only both endpoints of an edge xi yi in G[I1 O I2 ] for i OO .
Let S1 .
S2 .
Sk be subsets of S such that each Si consists of the vertices of S having the same neighbours in I1 O I2 .
Obviously, each Si consists of c-twin vertices, and we have Si O Sj = OI for i, j OO .
It then follows that the sets S1 .
S2 .
Sk correspond to a partition of S.
Hence.
G belongs to C(Kr K2 ).
Corollary 4.
Let G OO W2 .
Suppose that for DMI sets I1 and I2 , the set S = V (G) Oe (I1 O I2 ) induces a clique of size t in G.
If (G) = r Ou 4 and n = .
S|, then t = r and G = Kr K2 .
Lemma 4.
Let G OO W2 .
Suppose that for DMI sets I1 and I2 , the subgraph G Oe (I1 O I2 ) is a clique.
If (G) = 3, then G is in either C(G5 ) or C(G6 ) or C(K3 K2 ) .
ee Figures 3 and .
Proof.
Let I1 .
I2 be two DMI sets in G, and let S = V (G) Oe (I1 O I2 ) induce a clique of size t in G.
Suppose (G) = 3.
Then G has |S| 6 vertices.
Let I1 = .
1 , x2 , x3 }.
I2 = .
1 , y2 , y3 }.
1-well-covered graphs containing a clique of size n/3 Deniz We may assume .
1 y1 , x2 y2 , x3 y3 } OC E(G) by Theorem 2.
Observe that, by Proposition 4.
for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2.
It follows from Proposition 4.
2 that S has at least two vertices.
We first assume that every vertex in I1 O I2 has a neighbour in S.
Then |S| Ou 3, because for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2.
If G[I1 O I2 ] is isomorphic to 3K2 , then G belongs to C(K3 K2 ) as we deduce in the proof of Lemma 4.
Else, xi is adjacent to yj for some i, j OO .
, 2, .
with i = j.
Again, following from the proof of Lemma 4.
2, there exists u, v, w OO S such that I1 O I2 O .
, v, .
induces the graph G6 .
ee Figure .
If S has more than 3 vertices, then some vertices of S have to have the same neighbours in I1 O I2 .
Let S1 .
S2 .
Sk be subsets of S such that each Si consists of c-twin vertices of S.
It follows that the sets S1 .
S2 .
Sk corresponds to a partition of S.
Hence.
G belongs to C(G6 ).
Now, assume that there exist xi OO I1 for i OO .
, 2, .
such that xi has no neighbour in S.
Then yi OO NG (S) by Proposition 4.
2, and it follows from Corollary 2.
1 and Proposition 4.
that xi has only two neighbours yi , yj for an index j OO .
, 2, .
\ .
We therefore deduce that every vertex in S is adjacent to either yi or yj , since otherwise xi and its two neighbours yi , yj would survive in G Oe NG .
for some u OO S, however.
G Oe NG .
must consist of K2 components by Proposition 2.
1 and Lemma 2.
1, a contradiction.
Moreover, no vertex of S is adjacent to I2 Oe .
i , yj } by Proposition 4.
Then, there exists yEe OO I2 for Ee OO .
, 2, .
\ .
, .
such that yEe has no neighbour in S due to (G) = 3.
It then follows from Proposition 4.
2 that xEe OO NG (S), say xEe OO NG .
for a vertex u OO S.
Recall that u is adjacent to either yi or yj .
note that if u is adjacent to yi , then yj and its both neighbours xi , xj would survive in GOeNG .
, contradicting that G Oe NG .
consists of K2 components.
Therefore, u is adjacent to only yj in I2 .
This also implies that xj is adjacent to yEe since G Oe NG .
consists of K2 components.
On the other hand, there must be another vertex v OO S Oe u such that v OO NG .
i ) O S since xi OO / NG (S).
The vertex v must be adjacent to xj , since otherwise xj and its two neighbours yj , yEe would survive in G Oe NG .
, a contradiction.
Consequently.
G[I1 O I2 ] contains the edges xi yi , xj yj , xEe yEe , xi yj , xj yEe , and we will show that the graph G[I1 O I2 ] has no more edges.
For simplicity, we assume that i = 1, j = 2 and Ee = 3.
Since GOeNG .
consists of K2 components, we can say x1 y3 , x2 y1 OO / E(G).
By the same reason, x3 y2 OO / E(G) since G Oe NG .
consists of K2 components.
Similarly, x3 y1 OO / E(G), since otherwise NG .
1 ) would be dominated by .
2 , x3 }, contradicting that x1 is a shedding vertex.
Hence.
G[I1 O I2 ] consists of only the edges x1 y1 , x2 y2 , x3 y3 , x1 y2 , x2 y3 .
In addition, u .
has only neighbours x3 , y2 .
x2 , y1 ) in I1 O I2 .
Observe that I1 O I2 O .
, .
induces the subgraph G5 in G .
ee Figure .
Moreover, if S has more than two vertices, then every vertex in S Oe .
, .
must be c-twin with one of u, v.
Hence, we conclude that G is in C(G5 ).
Lemma 4.
Let G OO W2 .
Suppose that G Oe (I1 O I2 ) is a clique for DMI sets I1 and I2 .
If (G) = 2, then G belongs to one of the graph classes C(C5 ).
C(G2 ).
C(G3 ).
C(G4 ).
C(G7 ).
C(G8 ).
C(G9 ), and C(K2 K2 ) .
ee Figures 3 and .
Proof.
Let (G) = 2.
By Corollary 2.
G = C5 when |S| = 1.
We may therefore assume |S| Ou 2.
Let I1 = .
1 , x2 }.
I2 = .
1 , y2 }, and S = .
1 , u2 , .
, ut } for t Ou 2.
By Theorem 2.
1-well-covered graphs containing a clique of size n/3 Deniz Figure 6: The graphs G6 .
G7 .
G8 , and G9 .
we assume .
1 y1 , x2 y2 } OC E(G).
Notice that for each ui OO S, the graph G Oe NG .
i ] consists of K2 components by Proposition 2.
1 and Lemma 2.
1, since G Oe NG .
i ] OO W2 and S OC NG .
i ].
Also, by Proposition 4.
1, for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2.
First, we suppose that there exists a vertex of I1 O I2 having no neighbour in S.
Without loss of generality, we assume that x1 OO I1 has no neighbour in S.
Then y1 OO NG (S) by Proposition 4.
Also, x2 OO NG (S) by Proposition 4.
Since x1 has exactly two neighbours in I2 by Corollary 2.
1 and Proposition 4.
4, we may assume without loss of generality that y2 OO NG .
1 ), and so NG .
1 ) = .
1 , y2 }.
Notice that x2 y1 OO / E(G), since otherwise NG .
1 ) would be dominated by .
2 }, a contradiction as x1 is a shedding vertex.
It follows that G[I1 OI2 ] is isomorphic to a P4 whose middle vertices are x1 , y2 .
On the other hand, since x2 OO NG (S), we have two cases: y2 OO / N (S) or y2 OO N (S).
If y2 has no neighbour in S, then y1 has a neighbour in S.
It follows from Proposition 4.
4, every vertex in S is adjacent to both x2 and y1 in I1 O I2 .
This means that every pair of vertices in S is twin.
Hence.
G belongs to C(C5 ).
We now suppose that y2 OO N (S).
Since for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2, every vertex in S is adjacent to x2 and y1 .
r y2 ) where we recall that y1 OO NG (S).
It follows that there exists u, v OO S such that NG .
O (I1 O I2 ) = .
2 , y2 } and NG .
O (I1 O I2 ) = .
2 , y1 }.
Obviously, the set I1 O I2 O .
, .
induces the subgraph G3 in the graph G .
ee Figure .
Moreover, if S has more than 2 vertices, then every vertex in S Oe .
, .
would be a c-twin with u or v.
Hence.
G belongs to C(G3 ).
Let us next assume that every vertex in I1 O I2 has a neighbour in S.
Observe that if a vertex u OO S is adjacent to both xi and yj with i = j, then the edge xj yi must appear in G since G Oe NG .
consists of K2 components.
This means that that any vertex of S is adjacent to only both endpoints of either x1 y1 or x2 y2 when G[I1 O I2 ] induces 2K2 .
Then, by Proposition 2.
G belongs to C(K2 K2 ) when G[I1 O I2 ] induces 2K2 .
Hence, we further suppose that G[I1 O I2 ] ON 2K2 .
Without loss of generality, assume x1 y2 OO E(G).
We then observe that G[I1 O I2 ] is isomorphic to either P4 or C4 .
Suppose first that G[I1 O I2 ] induces P4 .
Then any vertex u OO S cannot be adjacent to both x1 and y2 in I1 O I2 , since otherwise G Oe NG .
would consists of two isolated vertices x2 , y1 due to G[I1 O I2 ] O = P4 , a contradiction.
This implies that if u OO S is a neighbour of x1 .
y2 ) in G, then u is adjacent to y1 .
x2 ).
It then follows from Proposition 4.
2 that there exist u, v OO S with u = v such that x1 , y1 OO NG .
and x2 , y2 OO NG .
Observe that G.
1 , x2 , y1 , y2 , u, .
is isomorphic to the graph G2 .
ee Figure .
If y1 and x2 have no common 1-well-covered graphs containing a clique of size n/3 Deniz neighbour in S, then G belongs to C(G2 ).
Otherwise, y1 and x2 have a common neighbour w in S, then G.
1 , x2 , y1 , y2 , u, v, .
is isomorphic to the graph G7 .
ee Figure .
Similarly, if S has some twin vertices in respect to u, v, w, then G belongs to C(G7 ).
Finally, we suppose that G[I1 O I2 ] is isomorphic to C4 .
Recall that for each vertex s OO S, the vertex s has a unique neighbour in IEe for Ee = 1, 2, also every vertex in I1 OI2 has a neighbour in S.
Then, we deduce that there exist u, v OO S such that .
, .
dominates all x1 , x2 , y1 , y2 in the graph G.
Since I1 O I2 induces C4 in G, we may then assume without loss of generality that x1 , y1 OO NG .
and x2 , y2 OO NG .
Obviously.
1 , x2 , y1 , y2 , u, .
is isomorphic to the graph G4 .
ee Figure .
Therefore.
G belongs to C(G4 ) when S = .
, .
or every vertex in S Oe .
, .
is a c-twin with one of u and v.
Now, we suppose that there exists w OO S Oe .
, .
such that w is not a c-twin with u and v.
Then w is adjacent to x1 , y2 .
r x2 , y1 ), assume without loss of generality that x1 , y2 OO NG .
In such a case.
1 , x2 , y1 , y2 , u, v, .
is isomorphic to the graph G8 .
ee Figure .
Therefore.
G belongs to C(G8 ) when S = .
, v, .
or each vertex of S Oe .
, v, .
is a c-twin with one of u, v, w.
At last, we suppose that there exists z OO S Oe .
, v, .
such that z is not a c-twin with u, v and w, then the only possibility is that x2 , y1 OO NG .
It follows that G.
1 , x2 , y1 , y2 , u, v, w, .
is isomorphic to the graph G9 .
ee Figure .
Also, if |S| Ou 5, then some vertices of S must form a c-twin with one of u, v, w, z.
Hence.
G belongs to C(G9 ).
Notice that any connected graph with independence number 1 is a complete graph.
Since all complete graphs having at least two vertices are in W2 , we say that any graph in W2 with independence number 1 belongs to C(K2 ).
By combining Lemmas 4.
2, 4.
3, 4.
4 and Proposition 4.
6, we get the promised characterization of W2 graphs for which G Oe (I1 O I2 ) is a clique for DMI sets I1 and I2 .
Theorem 1.
A connected graph G is in W2 such that the removal of two DMI sets from G leaves a clique if and only if G belongs to one of the graph classes C(G2 ).
C(G3 ), .
C(G9 ),
C(K2 ).
C(C5 ) and C(Kt K2 ) for t Ou 2.
Acknowledgement This research was supported by TUBITAK (The Scientific and Technological Research Council of Turke.
under the project number 121F018.
The author thanks the anonymous referee for their careful reading and invaluable comments.
References