Note on the Coalition Number of the d th Power of the n -Path

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 d th 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 } .