ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.09
https://doi.org/10.26493/1855-3974.3113.6f7
(Also available at http://amc-journal.eu)
Independent coalition in graphs:
existence and characterization
Mohammad Reza Samadzadeh , Doost Ali Mojdeh *
Department of Mathematics, Faculty of Mathematical Sciences,
University of Mazandaran, Babolsar, Iran
Received 2 May 2023, accepted 3 November 2023, published online 23 August 2024
Abstract
An independent coalition in a graph G consists of two disjoint sets of vertices V1 and
V2 neither of which is an independent dominating set but whose union V1 ∪ V2 is an inde-
pendent dominating set. An independent coalition partition, abbreviated, ic-partition, in a
graph G is a vertex partition π = {V1, V2, . . . , Vk} such that each set Vi of π either is a
singleton dominating set, or is not an independent dominating set but forms an independent
coalition with another set Vj ∈ π. The maximum number of classes of an ic-partition of
G is the independent coalition number of G, denoted by IC(G). In this paper, we study
the concept of ic-partition. In particular, we discuss the possibility of the existence of ic-
partitions in graphs and introduce a family of graphs for which no ic-partition exists. We
also determine the independent coalition number of some classes of graphs and investi-
gate graphs G of order n with IC(G) ∈ {1, 2, 3, 4, n} and the trees T of order n with
IC(T ) = n− 1.
Keywords: Independent coalition, independent coalition partition, independent dominating set, ido-
matic partition.
Math. Subj. Class. (2020): 05C69
1 Introduction
Let G = (V,E) denote a simple graph of order n with vertex set V = V (G) and edge set
E = E(G). The open neighborhood of a vertex v ∈ V is the set N(v) = {u|{u, v} ∈ E},
and its closed neighborhood is the set N [v] = N(v)∪{v}. Each vertex of N(v) is called a
neighbor of v, and the cardinality of N(v) is called the degree of v, denoted by deg(v) or
*Corresponding author.
E-mail addresses: m.samadzadeh02@umail.umz.ac.ir (Mohammad Reza Samadzadeh),
damojdeh@umz.ac.ir (Doost Ali Mojdeh)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.09
degG(v). A vertex v of degree 1 is called a pendant vertex or leaf, and its neighbor is called
a support vertex. A vertex of degree n− 1 is called a full vertex while a vertex of degree 0
is called an isolated vertex. The minimum and maximum degree of G are denoted by δ(G)
and ∆(G), respectively. For a set S of vertices of G, the subgraph induced by S is denoted
by G[S]. For two sets X and Y of vertices, let [X,Y ] denote the set of edges between X
and Y . If every vertex of X is adjacent to every vertex of Y , we say that [X,Y ] is full,
while if there are no edges between them, we say that [X,Y ] is empty. A subset Vi ⊆ V
is called a singleton set if |Vi| = 1, and is called a non-singleton set if |Vi| ≥ 2. The join
G+H of two disjoint graphs G and H is the graph obtained from the union of G and H by
adding every possible edge between the vertices of G and the vertices of H . We denote the
family of paths, cycles, complete graphs and stars of order n by Pn, Cn, Kn and K1,n−1,
respectively, and the complete k-partite graph with partite sets of order n1, n2, . . . , nk, by
Kn1,...,nk . A double star with respectively p and q leaves connected to each support vertex
is denoted by Sp,q . The complete graph K3 is called a triangle, and a graph is triangle-free
if it has no K3 as an induced subgraph. The girth of a graph with a cycle is the length of its
shortest cycle. For a graph G, the girth of G is denoted by g(G). For a graph G of order n,
let G denote the complement of G with V (G) = V (G) and E(G) = E(Kn)−E(G) [13].
A set S ⊆ V in a graph G = (V,E) is called a dominating set if every vertex v ∈ V
is either an element of S or is adjacent to an element of S. A set S ⊆ V is called an
independent set if its vertices are pairwise nonadjacent. The vertex independence number,
denoted by α(G), is the maximum cardinality of an independent set of G. An independent
dominating set in a graph G is a set which is both independent and dominating.
A partition of the vertices of G into dominating sets (independent dominating sets)
is called a domatic partition (idomatic partition). The maximum number of classes of a
domatic partition (idomatic partition) of G is called the domatic number (idomatic number)
of G, denoted by d(G) (id(G)). The concepts of domination and domatic partition and their
variations have been studied widely in the literature. See, for example, [1, 2, 3, 4, 5, 6, 12].
The term coalition was introduced by Haynes et al, [7] and has been studied further
in [8, 9, 10, 11].
Definition 1.1 ([7]). A coalition in a graph G consists of two disjoint sets of vertices
V1, V2 ⊂ V , neither of which is a dominating set but whose union V1 ∪ V2 is a dominating
set. We say that the sets V1 and V2 form a coalition, and are coalition partners.
Definition 1.2 ([7]). A coalition partition, henceforth called a c-partition, in a graph G
is a vertex partition π = {V1, V2, . . . , Vk} such that every set Vi of π is either a singleton
dominating set, or is not a dominating set but forms a coalition with another set Vj in π. The
coalition number C(G) equals the maximum order k of a c-partition of G, and a c-partition
of G having order C(G) is called a C(G)-partition.
Herein we will focus on coalitions involving independent dominating sets in graphs. In
other words, we will study the concepts of independent coalition and independent coalition
partition which have been introduced in [7] as an area for future research. We begin with
the following definitions.
Definition 1.3. An independent coalition in a graph G consists of two disjoint sets of
independent vertices V1 and V2, neither of which is an independent dominating set but
whose union V1 ∪ V2 is an independent dominating set. We say the sets V1 and V2 form an
independent coalition, and are independent coalition partners (or ic-partners).
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 3
Definition 1.4. An independent coalition partition, abbreviated ic-partition, in a graph G
is a vertex partition π = {V1, V2, . . . , Vk} such that every set Vi of π is either a singleton
dominating set, or is not an independent dominating set but forms an independent coalition
with another set Vj ∈ π. The independent coalition number IC(G) equals the maximum
number of classes of an ic-partition of G, and an ic-partition of G having order IC(G) is
called an IC(G)-partition.
Definition 1.5 ([8]). Let G be a graph of order n with vertex set V = {v1, v2, . . . , vn}.
The singleton partition, denoted π1, of G is the partition of V into n singleton sets, that is,
π1 = {{v1}, {v2}, . . . , {vn}}.
This paper is organized as follows. Section 1 is devoted to terminology and definitions.
We discuss the possibility of the existence of ic-partitions in graphs and derive some bounds
on independent coalition number in Section 2. In Section 3, we determine the independent
coalition number of some classes of graphs. The graphs G with IC(G) ∈ {1, 2, 3, 4}
are investigated in Section 4. In Section 5, we characterize triangle-free graphs G with
IC(G) = n and trees T with IC(T ) = n − 1. Finally, we end the paper with some
research problems.
2 Independent coalition partition: existence and bound
This section is divided into two subsections. In the first subsection, we show that not all
graphs admit an ic-partition, and in the second subsection, we present some bounds on
IC(G) whenever the graph G admits an ic-partition.
2.1 Existence
In the following definition, we construct graphs with arbitrarily large order for which no
ic-partition exists.
Definition 2.1. Let B be the set of all graphs obtained from the complete graph Kn, (n ≥ 4)
with the vertices vi, (1 ≤ i ≤ n), and two additional vertices vn+1, vn+2 such that vn+1
and vn+2 are adjacent to vn, and vn+1 is adjacent to vn−1. Figure 1 illustrates such a graph
for n = 4.
v1
v2 v3
v4
v5 v6
Figure 1: The graph G in B for n = 4.
Proposition 2.2. Let G be a graph. If G ∈ B, then G has no ic-partition.
Proof. Suppose, to the contrary, that G has an ic-partition π. The vertices v1, v2, . . . , vn−1
are pairwise adjacent, so they must be in different classes. Further, vn is a full vertex, so
it must be in a singleton class. Since vn−1 is adjacent to all vertices except vn+2, and
4 Ars Math. Contemp. 24 (2024) #P3.09
{vn−1, vn+2} dominates G, it follows that {vn−1} ∈ π. Further, since {vn−1} can only
form an independent coalition with {vn+2}, it follows that {vn+2} ∈ π. If {vn+1} ∈ π,
then π is a singleton partition. In this case, {vn+1} has no ic-partner, a contradiction.
Hence, {vn+1} /∈ π. It follows that π consists of a non-singleton set {vn+1, vi} such
that vi ∈ {v1, v2, . . . , vn−2}, and n singleton sets. Assume, without loss of generality,
that {vn+1, v1} ∈ π. Now for each 2 ≤ i ≤ n − 2, the set {vi} has no ic-partner, a
contradiction.
2.2 Bounds
Definition 1.4 implies that an ic-partition of a graph G is also a c-partition. Further, we
note that an ic-partition of G is a proper coloring as well. Hence, we have the following
two sharp bounds on IC(G). To see the sharpness of them, consider the complete graph
Kn.
Observation 2.3. Let G be a graph. If G has an ic-partition, then IC(G) ≤ C(G).
Furthermore, this bound is sharp.
Observation 2.4. Let G be a graph. If G has an ic-partition, then IC(G) ≥ χ(G). Fur-
thermore, this bound is sharp.
Given a connected graph G and an ic-partition π of it, the following theorem shows
that each set in π admits at most ∆(G) ic-partners.
Theorem 2.5. Let G be a connected graph with maximum degree ∆(G), and let π be an ic-
partition of G. If X ∈ π, then X is in at most ∆(G) independent coalitions. Furthermore,
this bound is sharp.
Proof. Let π be an ic-partition of G, and let X be a set in π. If X is a dominating set,
then it has no ic-partner. Hence, we may assume that X does not dominate G. Let x
be a vertex that is not dominated by X . Now every ic-partner of X must dominate x,
that is, it must contain a vertex in N [x]. Hence, there are at most |N [x]| ≤ ∆(G) + 1
sets in π that can form an independent coalition with X . Now we show that X cannot
form an independent coalition with ∆(G) + 1 sets. Suppose, to the contrary, that X has
∆(G) + 1 ic-partners (name V1, V2, . . . , V∆+1). Consequently, [X,Vi] is empty for each
1 ≤ i ≤ ∆(G) + 1. Let U =
⋃∆(G)+1
i=1 Vi, and G
′ = G[U ]. Consider an arbitrary vertex
v ∈ U (say v ∈ Vi) and an arbitrary set Vj such that 1 ≤ j ≤ ∆(G) + 1 and j ̸= i.
Since X ∪ Vj dominates G and [X,Vi] is empty, it follows that v has a neighbor in Vj .
Choosing Vj arbitrarily, we conclude that degG′(v) ≥ ∆(G), and so degG′(v) = ∆(G).
Hence, for each v ∈ U , we have degG′(v) = ∆(G). Now since G is connected, there
is a path P = (v0, v1, . . . , vk) connecting U to X such that v0 ∈ U and vk ∈ X . Note
that [U,X] is empty, and so V (P ) \ (U ∪ X) ̸= ∅. Let i be the smallest index for which
vi /∈ U ∪ X . It follows that vi−1 ∈ U , and so degG′(vi−1) = ∆(G). Thus, we have
degG(vi−1) ≥ degG′(vi−1) + 1 = ∆(G) + 1, a contradiction.
To prove the sharpness, let G be the graph that is obtained from the complete graph
Kn with vertices vi, (1 ≤ i ≤ n), and a path P2 = (a, b), where b is adjacent to v1. Let
A = {a}, B = {b} and Vi = {vi}, for 1 ≤ i ≤ n. One can observe that ∆(G) = n and
that the singleton partition π1 = {V1, V2, . . . , Vn, A,B} is an ic-partition of G such that A
forms an independent coalition with Vi, for each 1 ≤ i ≤ n. This completes the proof.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 5
Note that the bound presented in Theorem 2.5 does not hold for disconnected graphs.
As a counterexample, consider the graph G = K2 ∪ K2 and the singleton partition π1 of
it. On can verify that π1 is an ic-partition of G such that each set in π1 has two ic-partners,
while ∆(G) = 1.
The next bound relates independent coalition number of a graph to its idomatic number.
As we will see in the proof of Theorem 2.6, any graph admitting an idomatic partition has
an ic-partition. However, the converse is not necessarily true. For example, the singleton
partition of the cycle C5 is an ic-partition of it, while C5 has no idomatic partition. Or the
cycle C7 has the ic-partition π = {{v1, v5}, {v2, v4}, {v3}, {v6}, {v7}}, while it has no
idomatic partition.
Theorem 2.6. Let G be a connected graph, and let r ≥ 0 be the number of full vertices of
G. If G admits an idomatic partition, then IC(G) ≥ 2id(G)− r.
Proof. Let F = {v1, v2, . . . , vr} be the set of full vertices of G, and let π = {V1, V2, . . . ,
Vid(G)} be an idomatic partition of G of order id(G). Note that each full vertex must
be in a singleton set of π. Without loss of generality, assume that vi ∈ Vi, for each
1 ≤ i ≤ r. It follows that for each r + 1 ≤ i ≤ k, we have |Vi| ≥ 2. Now for
each r + 1 ≤ i ≤ k, we partition Vi into two nonempty subsets Vi,1 and Vi,2. Note
that no proper subset of Vi is a dominating set. Thus, neither Vi,1 nor Vi,2 is an in-
dependent dominating set, and so Vi,1 and Vi,2 are ic-partners. It follows that the par-
tition π′ = {V1, V2, . . . , Vr, Vr+1,1, Vr+1,2, Vr+2,1, Vr+2,2, . . . , Vid(G),1, Vid(G),2} is an
ic-partition of G of order 2id(G)− r. Hence, IC(G) ≥ 2id(G)− r.
3 Independent coalition number for some classes of graphs
Let us begin this section with some routine results.
Observation 3.1. For n ≥ 1, we have IC(Kn) = n.
Observation 3.2. For n ≥ 3, we have IC(K1,n−1) = 3.
Observation 3.3. For p, q ≥ 1, we have IC(Sp,q) = 4.
For complete multipartite graphs, the following result is obtained.
Proposition 3.4. Let G = Kn1,n2,...,nk be a complete k-partite graph with m ≥ 0 full
vertices (m partite sets of cardinality 1). Then IC(G) = 2k −m.
Proof. Let π = {V1, V2, . . . , Vk} be the partition of G into its partite sets. Assume, without
loss of generality, that the sets Vi, for 1 ≤ i ≤ m, are those containing full vertices. Now
for each m+ 1 ≤ i ≤ k, we partition Vi into two sets Vi,1 and Vi,2. Observe that Vi,1 and
Vi,2 are ic-partners, and so the partition π′ = {{V1}, {V2}, . . . , {Vm}, {Vm+1,1, Vm+1,2},
{Vm+2,1, Vm+2,2}, . . . , {Vk,1, Vk,2}} is an ic-partition of G of order 2k − m. Thus,
IC(G) ≥ 2k −m. Now let π′′ be an ic-partition of G. We note that π′′ has the following
properties:
• For any set S ∈ π′′, all vertices in S are in the same partite set of G.
• For any set Vi ∈ π, the vertices in Vi are in at most two sets of π′′.
Hence, we have IC(G) ≤ 2k −m, and so IC(G) = 2k −m.
6 Ars Math. Contemp. 24 (2024) #P3.09
Next we determine the independent coalition number of all paths and cycles.
Lemma 3.5 ([7]). For any path Pn, C(Pn) ≤ 6.
Theorem 3.6. For the path Pn,
IC(Pn) =

n if n ≤ 4;
4 if n = 5;
5 if n = 6, 7, 8, 9;
6 if n ≥ 10.
Proof. It is clear that for 1 ≤ n ≤ 4, we have IC(Pn) = n. Now let n = 5. Con-
sider the path P5 with V (P5) = {v1, v2, v3, v4, v5}. It is easily seen that IC(P5) ̸= 5.
Thus, IC(P5) ≤ 4. The partition {{v1, v3}, {v2}, {v4}, {v5}} is an ic-partition of P5, so
IC(P5) = 4. Now assume n = 6. Consider the path P6 with V (P6) = {v1, v2, v3, v4,
v5, v6}. It is clear that IC(P6) ̸= 6. The partition {{v1, v6}, {v2}, {v3}, {v4}, {v5}}
is an ic-partition of P6, so IC(P6) = 5. Next assume n = 7. Consider the path P7
with V (P7) = {v1, v2, v3, v4, v5, v6, v7}. By Lemma 3.5 and Observation 2.3, we have
IC(Pn) ≤ 6. Now we show that IC(P7) ̸= 6. Suppose that IC(P7) = 6. Let π be an
IC(P7)-partition. We note that π consists of a set (name A) of cardinality 2 and five sin-
gleton sets. Since γi(P7) = 3, each singleton set must be an ic-partner of A. On the other
hand, Theorem 2.5 implies that A has at most two ic-partners, a contradiction. The parti-
tion {{v1, v6}, {v2, v7}, {v3}, {v4}, {v5}} is an ic-partition of P7. Therefore, IC(P7) = 5.
Next we assume n = 8. Consider the path P8 with V (P8) = {v1, v2, v3, v4, v5, v6, v7, v8}.
By Lemma 3.5 and Observation 2.3, we have IC(Pn) ≤ 6. Now we show that IC(P8) ̸=
6. Suppose that IC(P8) = 6. Let π be an IC(P8)-partition. We consider two cases.
Case 1. π consists of a set (name A) of cardinality 3 and five singleton sets. Since
γi(P8) = 3, each singleton set must be an ic-partner of A. On the other hand, Theorem 2.5
implies that A has at most two ic-partners, a contradiction.
Case 2. π consists of two sets of cardinality 2 and four singleton sets. Since γi(P8) =
3, each singleton set must be an ic-partner of a set of cardinality 2. Therefore, using
Theorem 2.5, we deduce that for any two ic-partners C and D, it holds that |C∪D| = 3. On
the other hand, v3 and v6 are not present in any independent dominating set of cardinality
3, a contradiction.
The partition {{v1, v3, v6}, {v2, v7}, {v8}, {v4}, {v5}} is an ic-partition of P8. Therefore,
IC(P8) = 5.
Now let n = 9. Consider the path P9 with V (P9) = {v1, v2, v3, v4, v5, v6, v7, v8, v9}.
By Lemma 3.5 and Observation 2.3, we have IC(Pn) ≤ 6. Now we show that IC(P9) ̸=
6. Suppose that IC(P9) = 6. Let π be an IC(P9)-partition. There exist three cases.
Case 1. π consists of a set (name A) of cardinality 4 and five singleton sets. Since
γi(P9) = 3, each singleton set must be an ic-partner of A. On the other hand, by Theo-
rem 2.5, A has at most two ic-partners, a contradiction.
Case 2. π consists of a set (name A) of cardinality 3, a set (name B) of cardinality
2 and four singleton sets. Since γi(P9) = 3, no two singleton sets in π are ic-partners.
Furthermore, by Theorem 2.5, A has at most two ic-partners, so at least two singleton
sets of π must be ic-partners of B, which is impossible, as P9 has a unique independent
dominating set of cardinality 3.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 7
Case 3. π consists of three sets of cardinality 2, and three singleton sets. We note that
each singleton set in π must be an ic-partner of a set of cardinality 2, which is impossible,
as P9 has a unique independent dominating set of cardinality 3.
The partition {{v1, v3, v5}, {v2, v4, v9}, {v6}, {v7}, {v8}} is an ic-partition of P9.
Therefore, IC(P9) = 5.
Finally, let n ≥ 10. Consider the path Pn with V (Pn) = {v1, v2, . . . , vn}. By
Lemma 3.5 and Observation 2.3, we have IC(Pn) ≤ 6. Now we consider the sets
V1 = {v1, v6} ∪ {v2n−1 : n ≥ 5}, V2 = {v2, v5} ∪ {v2n : n ≥ 5}, V3 = {v3},
V4 = {v4}, V5 = {v7}, V6 = {v8}. Then π = {V1, V2, V3, V4, V5, V6} is an ic-partition
of Pn, where V3 and V4 are ic-partners of V1, and V5 and V6 are ic-partners of V2. So the
proof is complete.
Lemma 3.7 ([7]). For any cycle Cn, C(Cn) ≤ 6.
Lemma 3.7 and Observation 2.3 imply the following result.
Lemma 3.8. For any cycle Cn, IC(Cn) ≤ 6.
Lemma 3.9. For any cycle Cn with n ≥ 8 and n ≡ 0 (mod 2), it holds that IC(Cn) = 6.
Proof. Let V (Cn) = {v1, v2, . . . , vn}. Consider the sets V1 = {v1, v6}∪{v2n−1 : n ≥ 5},
V2 = {v2, v5} ∪ {v2n : n ≥ 5}, V3 = {v3}, V4 = {v4}, V5 = {v7}, V6 = {v8}.
Then π = {V1, V2, V3, V4, V5, V6} is an ic-partition of Cn, for n ≥ 8, where V3 and V4
are ic-partners of V1, and V5 and V6 are ic-partners of V2. Hence, by Lemma 3.8 and
Observation 2.3, we have IC(Cn) = 6.
Lemma 3.10. For any cycle Cn with n ≥ 8 and n ≡ 0 (mod 3), it holds that
IC(Cn) = 6.
Proof. Let V (Cn) = {v1, v2, . . . , v3k}. Consider the sets V1 = {v3i+1}, V2 = {v3i+2}
and V3 = {v3i+3}, for 0 ≤ i ≤ k − 1. Now for each 1 ≤ i ≤ 3, we partition Vi into
two nonempty sets Vi,1 and Vi,2. Observe that Vi,1 and Vi,2 are ic-partners. Hence, by
Lemma 3.8 and Observation 2.3, we have IC(Cn) = 6.
Lemma 3.11. For any cycle Cn with n ≥ 8 and n ≡ 5 (mod 6), it holds that
IC(Cn) = 6.
Proof. Assume n = 6k − 1, (k ≥ 2). Let V (Cn) = {v1, v2, . . . , vn}. Consider the sets
A =
k−1⋃
i=0
{v3i+1}, A1 =
2k−1⋃
i=k
{v3i+1}, A2 =
2k−1⋃
i=k
{v3i},
B =
2k⋃
i=k
{v3i−1}, B1 =
k−1⋃
i=1
{v3i−1}, B2 =
k−1⋃
i=1
{v3i}.
Let π = {A,A1, A2, B,B1, B2}. One can observe that π is an ic-partition of Cn,
where A1 and A2 are ic-partners of A, and B1 and B2 are ic-partners of B. Now using
Lemma 3.8 and Observation 2.3, we have IC(Cn) = 6.
Lemma 3.12. For any cycle Cn with n ≥ 8 and n ≡ 1 (mod 6), it holds that
IC(Cn) = 6.
8 Ars Math. Contemp. 24 (2024) #P3.09
Proof. Assume n = 6k + 1, (k ≥ 2). Let V (Cn) = {v1, v2, . . . , vn}. Consider the sets
A =
(
k⋃
i=0
{v3i+1}
)
∪ {v3k+3}, A1 =
2k⋃
i=k+2
{v3i}, A2 =
2k⋃
i=k+2
{v3i−1},
B =
(
2k⋃
i=k+1
{v3i+1}
)
∪ {v3k+2}, B1 =
k⋃
i=1
{v3i−1}, B2 =
k⋃
i=1
{v3i}.
Let π = {A,A1, A2, B,B1, B2}. One can observe that π is an ic-partition of Cn, where
A1 and A2 are ic-partners of A, and B1 and B2 are ic-partners of B. Now using Lemma 3.8
and Observation 2.3, we have IC(Cn) = 6.
Theorem 3.13. For the cycle Cn,
IC(Cn) =

n if n ≤ 6;
5 if n = 7;
6 if n ≥ 8.
Proof. If 1 ≤ n ≤ 6, then it is easy to check that IC(Cn) = n. Now assume n = 7. Con-
sider the cycle C7 with V (C7) = {v1, v2, v3, v4, v5, v6, v7}. First we show that IC(C7) ̸=
6. Suppose, to the contrary, that IC(C7) = 6. Let π be an IC(C7)-partition. We note that
π consists of five singleton sets and a set of cardinality 2 (name A). By Theorem 2.5, A has
at most two ic-partners. Hence, π contains two singleton sets that are ic-partners, which
contradicts the fact that γi(C7) = 3. The partition {{v1, v3}, {v5}, {v6}, {v4, v7}, {v2}}
is an ic-partition of C7, so IC(C7) = 5. Furthermore, by Lemmas 3.9, 3.10, 3.11 and 3.12
we have IC(Cn) = 6, for n ≥ 8.
4 Graphs with small independent coalition number
In this section we investigate graphs G with IC(G) ∈ {1, 2, 3, 4}. We will make use of the
following two lemmas.
Lemma 4.1. Let G be a graph of order n containing r ≥ 1 full vertices, and let
F = {v1, v2, . . . , vr} be the set of full vertices of G. Then IC(G) = k, if and only if
IC(G[V \ F ]) = k − r, where r < k ≤ n.
Proof. Assume first that IC(G[V \ F ]) = k − r. Let π = {V1, V2, . . . , Vk−r} be an
IC(G[V \F ])-partition. Now the partition π′ = {V1, V2, . . . , Vk−r, {v1}, {v2}, . . . , {vr}},
is an ic-partition of G, so IC(G) ≥ k. Now we prove that IC(G) = k. Suppose, to
the contrary, that IC(G) > k. Let π be an IC(G)-partition. Now the partition π′ = π \
{{v1}, {v2}, . . . , {vr}} is an ic-partition of G[V \F ] such that |π′| > k−r, a contradiction.
Hence, IC(G) = k. Conversely, assume that IC(G) = k. Let π be an IC(G)-partition.
Now the partition π′ = π \ {{v1}, {v2}, . . . , {vr}} is an ic-partition of G[V \ F ], so
IC(G[V \ F ]) ≥ k − r. Now we prove that IC(G[V \ F ]) = k − r. Suppose, to the
contrary, that IC(G[V \ F ]) > k − r. Let π be an IC(G[V \ F ])-partition. Now the
partition π′ = π ∪ {{v1}, {v2}, . . . , {vr}} is an ic-partition of G such that |π′| > k, a
contradiction. Hence, IC(G[V \ F ]) = k − r.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 9
Lemma 4.2. Let G be a graph containing a nonempty set of isolated vertices I . If IC(G) ≥
3, then for any IC(G)-partition π, there is a set Vr ∈ π such that Vr = I .
Proof. First we show that all vertices in I are in the same set of π. Suppose, to the contrary,
that there are sets Vi ∈ π and Vj ∈ π such that both Vi and Vj contain isolated vertices.
Let Vk ∈ π be an arbitrary set in π such that Vk /∈ {Vi, Vj}. (Since IC(G) ≥ 3, such a set
exists). Then Vk has no ic-partner, a contradiction. Now let Vr be the set in π containing
isolated vertices. Further, let v be an arbitrary vertex in Vr, and let u ∈ V (G) be an
arbitrary vertex such that u ̸= v. If u ∈ Vr, then u is not adjacent to v. Otherwise, the
set in π containing u is an ic-partner of Vr, which again implies that u is not adjacent to v.
Hence, we have deg(v) = 0. Choosing v arbitrarily, we conclude that Vr = I .
Proposition 4.3. Let G be a graph of order n. Then
(1) IC(G) = 1 if and only if G ≃ K1.
(2) IC(G) = 2 if and only if G ≃ K2 or G ≃ Kn, for some n ≥ 2.
Proof. (1) It is clear that IC(G) = 1 if and only if G ≃ K1.
(2) If G ≃ K2, then we clearly have IC(G) = 2. Now assume G ≃ Kn, for some n ≥ 2.
Let π be an ic-partition of G. Note that no more than two sets in π contain isolated vertices,
for otherwise, no two sets in π are ic-partners. Thus, |π| ≤ 2. Partitioning vertices of G into
two nonempty sets yields an ic-partition of G. Hence, IC(G) = 2. Conversely, suppose
that IC(G) = 2. Let π = {V1, V2} be an IC(G)-partition. If both V1 and V2 are singleton
dominating sets, then G ≃ K2. Hence, we may assume that at least one of them (say V1)
is not a singleton dominating set. It follows that V2 is not a singleton dominating set either,
for otherwise, G is a star, and so by Observation 3.2, we have IC(G) = 3. Hence, V1 and
V2 are ic-partners, and so V = V1 ∪ V2 is an independent set. Hence, G ≃ Kn, for some
n ≥ 2.
Definition 4.4. Let B1 represent the family of bipartite graphs H with partite sets H1 and
H2 such that |H1| ≥ 2, |H2| ≥ 2, δ(H) ≥ 1 and id(H) = 2.
Definition 4.5. For m ≥ 1, let B2 represent the family of graphs H ∪Km, where H is a
bipartite graph with δ(H) ≥ 1 and id(H) = 2.
Definition 4.6. For m ≥ 1, let B3 represent the family of graphs H ∪Km, where H is a
3-partite graph with δ(H) ≥ 1 and id(H) = 3.
Proposition 4.7. Let G be a graph. Then IC(G) = 3, if and only if G ∈ {K3,K1,n−1} ∪
B2.
Proof. Observations 3.1 and 3.2 imply that IC(K3) = 3 and that IC(K1,n−1) = 3, re-
spectively. Now let G ∈ B2. Let I be the set of isolated vertices of G, and let {H1, H2}
be a partition of G− I into its partite sets. We observe that the partition {I,H1, H2} is an
ic-partition of G, so IC(G) ≥ 3. Now we show that IC(G) = 3. Suppose, to the con-
trary, that IC(G) ≥ 4. Let π = {V1, V2, . . . , Vk} be an IC(G)-partition. By Lemma 4.2,
we have I ∈ {V1, V2, . . . , Vk}. Assume, without loss of generality, that I = V1. Now
for each 2 ≤ i ≤ k, Vi forms an independent coalition with V1, and so Vi dominates H .
Hence, the partition {V2, . . . , Vk} is an idomatic partition of H , which contradicts the as-
sumption. Hence, IC(G) = 3. Conversely, let G be a graph with IC(G) = 3, and let
10 Ars Math. Contemp. 24 (2024) #P3.09
π = {V1, V2, V3} be an IC(G)-partition. We consider four cases depending on the number
of full vertices of G.
Case 1. G has three full vertices. In this case, the sets V1, V2 and V3 are all singleton
dominating sets, so G ≃ K3.
Case 2. G has two full vertices. Note that this case never occurs.
Case 3. G has one full vertex. Let v1 be the full vertex of G. Lemma 4.1 implies that
IC(G − v1) = 2. Thus, by Proposition 4.3, either G − v1 ≃ K2, implying that G ≃ K3,
or G− v1 ≃ Kn, for some n ≥ 2, which implies that G ≃ K1,n−1, for some n ≥ 3.
Case 4. G has no full vertex. Let I be the set of isolated vertices of G. First we
note that V1, V2 and V3 are not pairwise ic-partners, for otherwise, we have G ≃ Kn,
and so by Proposition 4.3, we have IC(G) = 2, a contradiction. Hence, π contains a set
(say V1) that forms an independent coalition with V2 and V3, while V2 and V3 are not ic-
partners. Therefore, each vertex in V1 is an isolated vertex, so it follows from Lemma 4.2
that I = V1. Further, the sets V2 and V3 are independent dominating sets of G[V2 ∪ V3],
implying that id(G[V2 ∪ V3]) ≥ 2. It remains to show that id(G[V2 ∪ V3]) = 2. Suppose,
to the contrary, that id(G[V2 ∪ V3]) ≥ 3. Let π′ = {U1, U2, . . . , Uk}, (k ≥ 3), be an
idomatic partition of G[V2 ∪ V3]. Then the partition π′′ = {U1, U2, . . . , Uk, V1} is clearly
an ic-partition of G, implying that IC(G) ≥ 4, a contradiction. Hence, G ∈ B2.
Proposition 4.8. Let G be a graph. If IC(G) = 4, then G ∈ {K4,K2 +Kn,K1 +B} ∪
B1 ∪ B3, where n ≥ 2 and B ∈ B2.
Proof. Let π = {V1, V2, V3, V4} be an ic-partition of G. We consider two cases.
Case 1. G has a full vertex. Let v1 be a full vertex of G. Lemma 4.1 implies that
IC(G−v1) = 3. Thus, by Proposition 4.7, we have G−v1 ≃ K3, implying that G ≃ K4,
or G − v1 ≃ K1,n, for some n ≥ 2, implying that G ≃ K2 + Kn, for some n ≥ 2, or
G− v1 ∈ B2, which implies that G ≃ K1 +B, where B ∈ B2.
Case 2. G has no full vertex. First assume that G contains a nonempty set I of isolated
vertices. Then by Lemma 4.2, we have I ∈ π. Without loss of generality, assume that
I = V4. Now for each 1 ≤ i ≤ 3, Vi must form an independent coalition with I . Thus,
U = G[V1 ∪ V2 ∪ V3] is a 3-partite graph with id(U) ≥ 3. Since IC(G) = 4, the case
id(U) > 3 is impossible. Hence, id(U) = 3, and so G ∈ B3. Now assume that G contains
no isolated vertex. Since G has neither full vertices nor isolated vertices, each set of π has
either one or two ic-partners. If there is a set of π, (say V1) having one ic-partner, (say V2),
then it follows that V3 and V4 are ic-partners, and so G is a bipartitie graph with partite sets
V1 ∪ V2 and V3 ∪ V4. Otherwise, assume, without loss of generality, that V2 and V3 are
ic-partners of V1. It follows that V4 has an ic-partner in {V2, V3}. By symmetry, we may
assume that V4 and V3 are ic-partners. Then G is again a bipartitie graph with partite sets
V1 ∪ V2 and V3 ∪ V4. Now using Theorem 2.6, we have id(G) = 2, and so G ∈ B1.
5 Graphs with large independent coalition number
Our main goal in this section is to investigate structure of graphs G of order n with
IC(G) = n, under specified conditions. In addition, we will characterize all trees T of
order n with IC(T ) = n − 1. Let us begin with an observation that characterizes all
disconnected graphs G of order n with IC(G) = n.
Observation 5.1. Let G be a disconnected graph of order n. Then IC(G) = n if and only
if G ≃ Ks ∪Kr, for some s ≥ 1, and r ≥ 1.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 11
Now we introduce two sufficient conditions for a graph G of order n to have indepen-
dent coalition number n.
Observation 5.2. If G is a graph of order n with α(G) = 2, then IC(G) = n.
Proof. Let G be a graph of order n such that α(G) = 2. Consider the singleton partition
π1 of G. Note that for any two non-adjacent vertices v and u in V (G), the sets {v} and
{u} in π1, are ic-partners. Hence, π1 is an ic-partition of G, and so IC(G) = n.
Observation 5.3. Let G be a graph of order n. If G admits a partition of its vertices into
two maximal cliques, then IC(G) = n.
5.1 Graphs G with δ(G) = 1 and IC(G) = n
In this subsection, we characterize graphs G of order n with δ(G) = 1 and IC(G) = n.
We need the following definition.
Definition 5.4. Let G be a graph of order n, (n ≥ 3), and let δ(G) = 1. Furthermore, let
x be a pendant vertex of G, and let y be the support vertex of x. Then G ∈ F if and only
if V (G) \ {x, y} induces a clique.
Theorem 5.5. Let G be a graph of order n with δ(G) = 1. Then IC(G) = n if and only
if either G ≃ K2, or G ∈ F .
Proof. Obviously, IC(K2) = 2. Now assume that G ∈ F . Let x be a pendant vertex of G,
and let y be the support vertex of x. Further, let U = V (G) \ {x, y}. Note that U contains
no full vertex. If y is a full vertex, then G is obtained from the complete graph Kn−1, where
one of its vertices is adjacent to a leaf. In this case, we clearly have IC(G) = n. Thus,
we may assume that y is not a full vertex, that is, there is a vertex u ∈ U such that u is not
adjacent to y. Then it is easy to verify that the sets {y} and {u} are ic-partners, and that
each vertex in U \ {u} forms an independent coalition with {x}. Therefore, IC(G) = n.
Conversely, suppose that G is a graph with δ(G) = 1 and IC(G) = n. Let x be a leaf
of G, and let y be the support vertex of x. Consider the singleton partition π1 of G. Note
that each set in π1\{{x}, {y}} must be an ic-partner of {x} or {y}, to dominate x. Let
A = N(y) \ {x}, and B = V (G) \ ({x, y} ∪A). We consider four cases.
Case 1. A = ∅ and B = ∅. In this case, we have G ≃ K2.
Case 2. A = ∅ and B ̸= ∅. By Observation 5.1, we have G ≃ K2 ∪ Kr, for some
r ≥ 1. Thus, G ∈ F .
Case 3. A ̸= ∅ and B = ∅. For each v ∈ A, the set {v} cannot be an ic-partner of {y},
so it must be an ic-partner of {x}. This implies that A induces a clique. Hence, G ∈ F .
Case 4. A ̸= ∅ and B ̸= ∅. For each v ∈ A, the set {v} cannot be an ic-partner of
{y}, so it must be an ic-partner of {x}. This implies that [A,B] is full and that A induces
a clique. Now for each vertex u ∈ B, in order for the set {u} to be an ic-partner of {x}
or {y}, u must be adjacent to all other vertices in B. Hence, B induces a clique, and so
G ∈ F , which completes the proof.
As an immediate result from Theorem 5.5 we have:
Corollary 5.6. Let T be a tree of order n. Then IC(T ) = n if and only if T ∈ {P1, P2,
P3, P4}.
12 Ars Math. Contemp. 24 (2024) #P3.09
5.2 Triangle-free graphs G with IC(G) = n
In this subsection, we characterize graphs G of order n with g(G) = 4 and IC(G) = n.
This will lead to characterization of all triangle-free graphs G of order n with IC(G) = n.
We will make use the following lemmas.
Lemma 5.7. Let G be a triangle-free graph of order n with IC(G) = n. Then g(G) ≤ 6.
Proof. Let G be a graph of order n with IC(G) = n, and suppose, to the contrary, that
g(G) ≥ 7. Let C ⊆ G be a cycle of order g(G). Consider an arbitrary vertex v ∈ V (C).
Note that γi(C) ≥ 3, and so {v} is not an ic-partner of any set {u} ⊂ V (C). Therefore,
it must be an ic-partner of a set {u} ⊆ V (G) \ V (C). It follows that, {u} dominates
V (C) \Nc[v], which implies that G contains triangles, a contradiction.
Lemma 5.8. Let G be a graph of order n with g(G) = 6. Then IC(G) = n if and only if
G ≃ C6.
Proof. Let G be a graph of order n with g(G) = 6. If G ≃ C6, then by Theorem 3.13,
we have IC(G) = 6. Conversely, assume that IC(G) = n. Let C ⊆ G be a cycle of
order 6, and suppose, to the contrary, that V (G) \ V (C) ̸= ∅. Consider an arbitrary vertex
v ∈ V (G) \ V (C). If {v} is an ic-partner of a set {u} ⊂ V (C), then {v} must dominate
V (C) \ Nc[u], which implies that G contains triangles, a contradiction. Otherwise, {v}
must be an ic-partner of a set {u} ⊂ V (G) \ V (C). Now since {u, v} dominates C, it
follows that G contains triangles, or induces cycles of order 4, a contradiction.
Our next result can be established almost the same way as Lemma 5.8, so we state it
without proof.
Lemma 5.9. Let G be a graph of order n with g(G) = 5. Then IC(G) = n if and only if
G ≃ C5.
In order to characterize graphs G of order n with IC(G) = n and g(G) = 4, we need
the following definitions.
Definition 5.10. Let K0 represent a bipartite graph with partite sets H1 = {v1, v2, v3, v4}
and H2 = {u1, u2, u3, u4} such that for each 1 ≤ i ≤ 4, vi is adjacent to all vertices in
H2, except ui (see Figure 2).
Definition 5.11. Let K represent a family of 4-partite graphs with partite sets
H1 = {v1, v2, v3, v4}, H2 = {u1, u2, u3, u4}, H3 = {n1, n2, . . . , nk} and
H4 = {m1,m2, . . . ,mk}, for k ≥ 1, with the following properties:
• [H1, H3] is full and [H2, H4] is full,
• [H1, H4] is empty and [H2, H3] is empty,
• For each 1 ≤ i ≤ 4, vi is adjacent to all vertices in H2, except ui,
• For each 1 ≤ i ≤ k, ni is adjacent to all vertices in H4, except mi.
Figure 3 illustrates such a graph for k = 3.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 13
v1 v2 v3 v4
u1 u2 u3 u4
Figure 2: The graph K0.
v1
v2
v3
v4 u4
u3
u2
u1
n1
n2
n3 m3
m2
m1
Figure 3: The graph in K for k = 3.
Theorem 5.12. Let G be a graph of order n with g(G) = 4. Then IC(G) = n if and only
if G ∈ {C4,K0} ∪ K.
Proof. It is easy to check that IC(C4) = 4 and that IC(K0) = 8. Now let G ∈ K.
We observe that for each 1 ≤ i ≤ 4, {vi} and {ui} are ic-partners, and that for each
1 ≤ i ≤ k, {ni} and {mi} are ic-partners. Thus, IC(G) = n. Conversely, let G be a
graph of order n with g(G) = 4 and IC(G) = n, and let C be a cycle of G of order 4
with V (C) = {x, y, z, t} and E(C) = {xy, yz, zt, tx}. If G = C, then the desired result
follows. Hence, we assume that G ̸= C. Since x is adjacent to y and t, neither {y} nor {t}
is an ic-partner of {x}. Now consider two cases.
Case 1. {x} and {z} are ic-partners. In this case, G is dominated by {x, z}. Let
A = N(x) \ {y, t} and B = N(z) \ {y, t}. If A ̸= ∅, (say v ∈ A), then it is not difficult
to check that {v} has no ic-partner. Thus, A = ∅, and so by symmetry, we have B = ∅.
Hence, G ≃ C4.
Case 2. {x} and {z} are not ic-partners. Let {e} be an ic-partner of {x}. Since {x, e}
dominates G and z is not adjacent to x, it must be adjacent to e. Let A = N(x) \ {y, t}
and B = N(e) \ {z}. It is not difficult to verify that A ∩ B = ∅. Now if A = ∅, then
{z} cannot form an independent coalition with any other set, so A ̸= ∅. Let {f} ⊆ A be
an ic-partner of {z}. We note that if a set {g} forms an independent coalition with {y},
then g ∈ B. Further, if a set {h} forms an independent coalition with {t} then h ∈ B. Let
{g} and {h} be ic-partners of {y} and {t}, respectively. Observe that {g} ≠ {h}. Now let
A′ = A \ {f} and B′ = B \ {g, h}. There exist the following subcases.
14 Ars Math. Contemp. 24 (2024) #P3.09
Subcase 2.1. A′ = ∅ and B′ = ∅. In this case, we have G ≃ K0.
Subcase 2.2. A′ = ∅ and B′ ̸= ∅. Let v ∈ B′. One can verify that {v} cannot form an
independent coalition with any other set. Thus, this case is impossible.
Subcase 2.3. A′ ̸= ∅ and B′ = ∅. Let v ∈ A′. One can verify that {v} cannot form an
independent coalition with any other set. Thus, this case is impossible.
Subcase 2.4. A′ ̸= ∅ and B′ ̸= ∅. Let v ∈ A′. If a set {u} forms an independent
coalition with {v}, then u ∈ B′. Furthermore, for each vertex u ∈ B′, {u} cannot form
an independent coalition with more than one sets {v} ⊆ A′. Thus, |A′| ≤ |B′|. Using
a similar argument, we deduce that |B′| ≤ |A′|, and so |A′| = |B′|. Consequently, the
following statements hold in the graph G:
• G[{x, y, z, t, e, f, g, h}] is a bipartite graph with partite sets V1 = {x, z, g, h} and
V2 = {y, t, e, f}, which is isomorphic to K0,
• [V1, A′] is full and [V2, B′] is full,
• [V1, B′] is empty and [V2, A′] is empty,
• G[A′∪B′] is a bipartite graph with partite sets A′ and B′ such that degG[A′∪B′](v) =
|A′| − 1 = |B′| − 1, for each v ∈ A′ ∪B′.
Hence, G ∈ K and the proof is complete.
Using Observation 5.1, Corollary 5.6, Lemmas 5.7, 5.8 and 5.9, and Theorem 5.12, we
infer the following result.
Corollary 5.13. Let G be a triangle-free graph of order n. Then IC(G) = n if and only if
G ∈ {C4, C5, C6, P1, P2, P3, P4,K2,K1 ∪K2,K2 ∪K2,K0} ∪ K.
5.3 Trees T with IC(T ) = n − 1
The following theorem characterizes all trees T of order n with IC(T ) = n− 1.
Theorem 5.14. Let T be a tree of order n. Then IC(T ) = n − 1 if and only if T ∈
{P5, P6, S1,2,K1,3}.
Proof. By Theorem 3.6, we have IC(P5) = 4 and IC(P6) = 5. Further, by Observa-
tion 3.2, we have IC(K1,3) = 3 and by Observation 3.3, we have IC(S1,2) = 4. Con-
versely, let T be a tree of order n with IC(T ) = n − 1, where x is a leaf, and y is the
support vertex of x. Define A = N(y) \ {x} and B = V (G) \ ({x, y} ∪ A). Further,
let π be an IC(T )-partition. Note that π contains a set of cardinality 2 (say V1 = {u, v})
and n − 2 singleton sets. Since x and y are adjacent, we have V1 ̸= {x, y}. Note as well
that any set in π must be an ic-partner of the set containing x, or the set containing y, to
dominate x. We consider two cases.
Case 1. B = ∅. If A = ∅, then we have T ≃ K2, and so IC(T ) = 2 ̸= n− 1. Hence,
A ̸= ∅, and so T ≃ K1,n−1, for some n ≥ 3. Now by Lemma 3.7, we have IC(T ) = 3.
Hence, T ≃ K1,3.
Case 2. B ̸= ∅. Since T is connected, we have A ̸= ∅. We divide this case into some
subcases.
Subcase 2.1. u ∈ A and v ∈ B. We first show that |A| = 1. Suppose, to the contrary,
that |A| ≥ 2. Then there is a vertex z ∈ A such that z ̸= u. Since z and y are adjacent,
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 15
{z} cannot be an ic-partner of {y}, so it must be an ic-partner of {x}. Since {x} does not
dominate u, u must be adjacent to z, which is a contradiction, since y, z and u induce a
triangle. Now {y} cannot be an ic-partner of {x} or {u, v}, so it must have an ic-partner
in B. This implies that |B| ≥ 2. Let {t} ⊂ B be an ic-partner of {y}. we show that
B \ {v, t} = ∅. Suppose that B \ {v, t} ̸= ∅. Let z ∈ B \ {v, t}. Note that v and t are
adjacent. Now {z} must be an ic-partner of {x} or {y}, so z must be adjacent to t and
v, which is a contradiction, since z, t and v induce a triangle. Hence, B = {v, t} and so
T ≃ P5.
Subcase 2.2. {u, v} ⊆ B. An argument similar to the one presented above implies
that |A| = 1. Now we show that B \ {u, v} = ∅. Suppose that B \ {u, v} ≠ ∅. Let
z ∈ B \ {u, v}, and let A = {t}. Since t and y are adjacent, {t} cannot be an ic-partner
of {y}, so it must be an ic-partner of {x}. Thus, t must be adjacent to u, v and z. Now
{z} must be an ic-partner of {x} or {y}, so z must be adjacent to u and v, which is a
contradiction, since z, u and t induce a triangle. Hence, T ≃ S1,2.
Subcase 2.3. {u, v} ⊆ A. We first show that A\{u, v} = ∅. Suppose that A\{u, v} ≠
∅. Let z ∈ A \ {u, v}. Since z is adjacent to y, {z} must be an ic-partner of {x}, so z must
be adjacent to u and v, which is a contradiction, since z, u and y induce a triangle. Now
we show that |B| = 1. Suppose that |B| ≠ 1. First assume |B| ≥ 3. Let z, t, w ∈ B. Now
z, t and w induce a triangle, since the sets containing each of them, must be an ic-partner
of {x} or {y}, a contradiction. Now assume |B| = 2. Let B = {z, t}. Each of the sets
{z} and {t} must be an ic-partner of {x} or {y}. Thus, z must be adjacent to t. Now
{u, v} must be an ic-partner of {x}, so z and t must be dominated by {u, v}. Now the
induced subgraph T [{u, v, z, t}] contains at least one cycle, a contradiction. Hence, we
have T ≃ S1,2.
Subcase 2.4. u = y and v ∈ B. we first show that |A| = 1. Suppose that |A| ≥ 2.
Let z, t ∈ A. Since z and t are adjacent to y, {z} and {t} cannot be an ic-partner of y,
so each of them must be an ic-partner of {x}. Thus, z must be adjacent to t, which is a
contradiction, since z, t and y induce a triangle. Now we show that |B| = 2. Suppose that
|B| ̸= 2 . If |B| = 1, then T ≃ P4, a contradiction. Otherwise, let {v, z, t} ⊆ B and
A = {w}. Now {w} cannot be an ic-partner of {u, v}, so it must be an ic-partner of {x}.
Thus, w must be adjacent to v, z and t. Now observe that {u, v} must have an ic-partner
in B. Assume, without loss of generality, that {u, v} and {z} are ic-partners. This implies
that t is adjacent to z or v, which is impossible, since both cases lead to existence of an
induced triangle. Hence, T ≃ S1,2.
Subcase 2.5. u = x and v ∈ A. We first show that |B| ≤ 2. Suppose that |B| ≥ 3.
Let {z, t, w} ⊆ B. Note that {y} must have an ic-partner in B. Assume, without loss of
generality, that {y} and {z} are ic-partners. It follows that z is adjacent to t and w. Now if
{y} is an ic-partner of {t} or {w}, then t must be adjacent to w, which is impossible, since
z, t and w induce a triangle. Hence, both t and w must be ic-partners of {u, v}, which
implies that t is adjacent to w. Now z, t and w induce a triangle, a contradiction. Now we
show that |A| ≤ 2. Suppose that |A| ≥ 3. Let {z, t, v} ⊆ A. The sets {z} and {t} must be
ic-partners of {u, v}. This implies that z is adjacent to t. Now z, t and y induce a triangle,
a contradiction. Further, we observe that the case |A| = |B| = 2 is impossible. Hence,
either |A| = 2 and |B| = 1, which implies that T ≃ S1,2, or |A| = 1 and |B| = 2, which
implies that T ≃ P5.
Subcase 2.6. u = x and v ∈ B. We first show that |A| = 1. Suppose that |A| ≥ 2.
Let {z, t} ⊆ A. Now each of the sets {z} and {t} must be an ic-partner of {u, v}. This
16 Ars Math. Contemp. 24 (2024) #P3.09
implies that z is adjacent to t, which is a contradiction, since y, z and t induce a triangle.
Now we show that |B| ≤ 3. Suppose that |B| ≥ 4. Let {v, t, w, h} ⊆ B and A = {z}.
Note that {y} must have an ic-partner in B. Assume, without loss of generality, that {y}
and {t} are ic-partners. It follows that t is adjacent to w, h and v. Now {w} must be an
ic-partner of {y} or {u, v}. One can observe that both cases lead to contradiction. Hence,
either |B| = 2, which implies that T ≃ P5, or |B| = 3, which implies that T ≃ P6.
6 Discussion and conclusions
In Proposition 2.2, we introduced a family of graphs admitting no ic-partition. This result
motivates the following problem:
Problem 6.1. Characterize graphs admitting an ic-partition.
In Observations 2.3 and 2.4, we presented the sharp inequalities IC(G) ≤ C(G) and
IC(G) ≥ χ(G). This raises the following problems:
Problem 6.2. Characterize graphs G in which the equality IC(G) = C(G) holds.
Problem 6.3. Characterize graphs G in which the equality IC(G) = χ(G) holds.
In Theorem 5.14, trees T of order n, with IC(T ) = n − 1 have been characterized.
This raises the following problem:
Problem 6.4. Characterize graphs G of order n with IC(G) = n− 1.
ORCID iDs
Mohammad Reza Samadzadeh https://orcid.org/0009-0004-4370-5905
Doost Ali Mojdeh https://orcid.org/0000-0001-9373-3390
References
[1] A. Buğra Özer, E. Saygı and Z. Saygı, Domination type parameters of Pell graphs, Ars Math.
Contemp. 23 (2023), Paper No. 1.03, 12 pp., doi:10.26493/1855-3974.2637.f61, https://
doi.org/10.26493/1855-3974.2637.f61.
[2] A. Cabrera Martı́nez, A note on the k-tuple domination number of graphs, Ars Math. Contemp.
22 (2022), Paper No. 4.03, 5 pp., doi:10.26493/1855-3974.2600.dcc, https://doi.org/
10.26493/1855-3974.2600.dcc.
[3] A. Cabrera Martı́nez, A. Estrada-Moreno and J. A. Rodrı́guez-Velázquez, From Italian dom-
ination in lexicographic product graphs to w-domination in graphs, Ars Math. Contemp. 22
(2022), Paper No. 1.04, 25 pp., doi:10.26493/1855-3974.2318.fb9, https://doi.org/
10.26493/1855-3974.2318.fb9.
[4] G. J. Chang, The domatic number problem, volume 125, pp. 115–122, 1994, doi:10.1016/
0012-365X(94)90151-1, https://doi.org/10.1016/0012-365X(94)90151-1.
[5] A. Gorzkowska, M. A. Henning, M. Pilśniak and E. Tumidajewicz, Paired domination stability
in graphs, Ars Math. Contemp. 22 (2022), Paper No. 2.04, 18 pp., doi:10.26493/1855-3974.
2522.eb3, https://doi.org/10.26493/1855-3974.2522.eb3.
[6] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. McRae and N. Phillips, The upper domatic
number of a graph, AKCE Int. J. Graphs Comb. 17 (2020), 139–148, doi:10.1016/j.akcej.2018.
09.003, https://doi.org/10.1016/j.akcej.2018.09.003.
M. R. Samadzadeh and D. A. Mojdeh: Independent coalition in graphs: existence and . . . 17
[7] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Introduction to
coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020), 653–659, doi:10.1080/09728600.
2020.1832874, https://doi.org/10.1080/09728600.2020.1832874.
[8] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Upper bounds
on the coalition number, Australas. J. Comb. 80 (2021), 442–453, https://ajc.maths.
uq.edu.au/pdf/80/ajc_v80_p442.pdf.
[9] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Coalition
graphs, Commun. Comb. Optim. 8 (2023), 423–430, doi:10.22049/CCO.2022.27916.1394,
https://doi.org/10.22049/CCO.2022.27916.1394.
[10] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Coalition
graphs of paths, cycles, and trees, Discuss. Math. Graph Theory 43 (2023), 931–946, doi:
10.7151/dmgt.2416, https://doi.org/10.7151/dmgt.2416.
[11] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae and R. Mohan, Self-coalition
graphs, Opuscula Math. 43 (2023), 173–183, doi:10.7494/opmath.2023.43.2.173, https://
doi.org/10.7494/opmath.2023.43.2.173.
[12] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, vol-
ume 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc.,
New York, 1998.
[13] D. B. West, Introduction to Graph Theory, Prentice Hall, NJ, 2nd edition, 2001.