Search

A set S of vertices in a graph G is a dominating set if every vertex of V (G) \ S is adjacent to a vertex in S. A coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a dominating set but whose union X ∪ Y is a dominating set of G. Such sets X and Y form a coalition in G. A coalition partition, abbreviated c-partition, in G is a partition X = { X 1 , ... , X k } of the vertex set V(G) of G such that for all i ∈ [ k ] , each set X i ∈ X satisfies one of the following two conditions: (1) X i is a dominating set of G with a single vertex, or (2) X i forms a coalition with some other set X j ∈ X . Let A = { A 1 , ... , A r } and B = { B 1 , ... , B s } be two partitions of V(G). Partition B is a refinement of partition A if every set B i ∈ B is either equal to, or a proper subset of, some set A j ∈ A . Further if A ≠ B , then B is a proper refinement of A . Partition A is a minimal c-partition if it is not a proper refinement of another c-partition. Haynes et al. [AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659] defined the minmin coalition number c min (G) of G to equal the minimum order of a minimal c-partition of G. We show that 2 ≤ c min (G) ≤ n , and we characterize graphs G of order n satisfying c min (G) = n . A polynomial-time algorithm is given to determine if c min (G) = 2 for a given graph G. A necessary and sufficient condition for a graph G to satisfy c min (G) ≥ 3 is given, and a characterization of graphs G with minimum degree 2 and c min (G) = 4 is provided. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and order n = | V | . A coalition in G is a combination of two distinct sets, A ⊆ V and B ⊆ V , which are disjoint and are not dominating sets of G, but their union A ∪ B is a dominating set of G. A coalition partition of G is a partition P = { S 1 , ... , S k } of its vertex set V, where each set S i ∈ P is either a dominating set of G with only one vertex, or it is not a dominating set but forms a coalition with some other set S j ∈ P . The coalition number C(G) is the maximum cardinality of a coalition partition of G. To represent a coalition partition P of G, a coalition graph CG (G , P) is created, where each vertex of the graph corresponds to a member of P and two vertices are adjacent if and only if their corresponding sets form a coalition in G. A coalition partition P of G is a singleton coalition partition if every set in P consists of a single vertex. If a graph G has a singleton coalition partition, then G is referred to as a singleton-partition graph. A graph H is called a singleton coalition graph of a graph G if there exists a singleton coalition partition P of G such that the coalition graph CG (G , P) is isomorphic to H. A singleton coalition graph chain with an initial graph G 1 is defined as the sequence G 1 → G 2 → G 3 → ⋯ where all graphs G i are singleton-partition graphs, and CG (G i , Γ 1) = G i + 1 , where Γ 1 represents a singleton coalition partition of G i . In this paper, we address two open problems posed by Haynes et al. We characterize all graphs G of order n and minimum degree δ (G) = 2 such that C (G) = n . Additionally, we investigate the singleton coalition graph chain starting with graphs G, where δ (G) ≤ 2 . [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and of order n = | V | , and let δ (G) and Δ (G) be the minimum and maximum degree of G, respectively. Two disjoint sets V 1 , V 2 ⊆ V form a coalition in G if none of them is a dominating set of G but their union V 1 ∪ V 2 is. A vertex partition Ψ = { V 1 , … , V k } of V is a coalition partition of G if every set V i ∈ Ψ is either a dominating set of G with the cardinality | V i | = 1 , or is not a dominating set, but for some V j ∈ Ψ , V i and V j form a coalition. The maximum cardinality of a coalition partition of G is the coalition number C (G) of G. Given a coalition partition Ψ = { V 1 , … , V k } of G, a coalition graph CG (G , Ψ) is associated on Ψ such that there is a one-to-one correspondence between its vertices and the members of Ψ , where two vertices of CG (G , Ψ) are adjacent if and only if the corresponding sets form a coalition in G. In this paper, we address previously some open problems in the study of the coalitions in graphs. We characterize all graphs G with δ (G) ≤ 1 and C (G) = n , and we characterize all trees T with C (T) = n - 1 . We determine the number of coalition graphs that can be defined by all coalition partitions of a given path. Furthermore, we show that there is no universal coalition path, a path whose coalition partitions define all possible coalition graphs. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a graph. A subset S⊆V is a k-dominating set of G if each vertex in V-S is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs P(5k+1,2) and P(5k+2,2), for k>0, is 4k+2 and 4k+3, respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and P(5k+4,3). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs P(5k+1,3),P(5k+2,3) and P(5k+3,3). [ABSTRACT FROM AUTHOR]