Balanced Domination in Convex Polytopes, Trees, and Grid Graphs

2025/11/09 by Nikolic, Bojan, Djukanovic, Marko
Computer Science · #05C50 #05C69 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems

paper · doi:10.48550/arxiv.2511.06539

openalex publication_date 2025/11/09 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28

Abstract

This paper addresses two open questions posed in [27] regarding the balanced domination number in graphs. We show that three new classes of graphs, those of convex polytopes A_n, D_n, and Rn'', are d-balanced. Further, we provide a characterization of d-balancedness for rooted trees with two levels of descendants and prove that each full binary tree is d-balanced. Several results for caterpillar graphs are established. Moreover, we determine and prove the exact balanced domination number for grid graphs. Finally, we conclude by providing several open problems of interest.

Related

• Balanced vertices in labeled rooted trees
• Fair Domination in Graphs
• Facets of the Total Matching Polytope for bipartite graphs
• Sampling Balanced Forests of Grids in Polynomial Time
• On total domination subdivision numbers of trees