TITLE:
Note on the Coalition Number of the dth Power of the n-Path
AUTHORS:
Qinglin Jia, Wenwei Zhao, Zhengyuan Jiang, Yongqiang Zhao
KEYWORDS:
Coalition, Coalition Partition, Coalition Number, Dominating Set
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.15 No.2,
March
28,
2025
ABSTRACT: In a graph
G=(
V,E
)
, two disjoint sets
V
1
,
V
2
⊆V
are said to form a coalition, if neither
V
1
nor
V
2
is a dominating set of
G
, but
V
1
∪
V
2
is a dominating set of
G
. The sets
V
1
and
V
2
forming a coalition are said to be coalition partners. A coalition partition, called a c-partition, is a vertex partition
π={
V
1
,
V
2
,⋯,
V
k
}
such that each
V
i
∈π
satisfies the following conditions:
V
i
is a singleton dominating set of
G
, or
V
i
is not a dominating set of
G
but has a coalition partner
V
j
∈π
, a non-dominating set of
G
. The maximum order
k
of a c-partition of
G
is called the coalition number, denoted by
C(
G
)
. In this paper, we study the coalition numbers of the dth power of the n-path
P
n
d
, get the exact values of
C(
P
n
d
)
for enough large
n
, and also provide some bounds of
C(
P
n
d
)
for the other cases. As a special case, we get the exact values of
C(
P
n
2
)
except for
n∈{
11,12,⋯,20 }
.