On cubic graphs having the maximal coalition number

2024/04/09 by Andrey A. Dobrynin, Dobrynin, Andrey A., Hamidreza Golmohammadi +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2404.06245

openalex publication_date 2024/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A coalition in a graph G with vertex set V consists of two disjoint sets V₁, V₂⊂ V such that neither V₁ nor V₂ is a dominating set, but the union V₁∪ V₂ is a dominating set in G. A partition of graph vertices is called a coalition partition P if every non-dominating set of P is a member of a coalition and every dominating set is a single-vertex set. The coalition number C(G) of a graph G is the maximum cardinality of its coalition partition. It is known that for cubic graphs C(G)≤ 9. The existence of cubic graphs with the maximal coalition number is an unsolved problem. In this paper, an infinite family of cubic graphs satisfying C(G)=9 is constructed.

Cited by

• Coalition graphs of connected domination partitions in subcubic graphs

Related

• Coalition of cubic graphs of order at most 10
• On k-coalition in graphs: bounds and exact values
• Total k-coalition: bounds, exact values and an application to double coalition
• k-Coalitions in Graphs
• On Coalition Graphs and Coalition Count of Graphs