Effects of Subdivision on Fair Domination in Cyclic Structures
Authors: G. Navamani  
Published: January 2025

A fair dominating set (FDS) is a dominating set of a graph , such that all vertices in are dominated by the same number of vertices of . The fair domination number (FDN) is the minimum cardinality of a fair dominating set of , denoted by The domination subdivision number (FDSN) , represents the smallest number of edges in that needs to be subdivided (with each edge being subdivided at most once) to increase the domination number of the graph. The fair domination subdivision number, (or ) is the minimum number of edge subdivisions needed to be applied to the graph to increase (or decrease) the fair domination number of the graph. In this paper, we present the fair domination subdivision numbers for Cycle with Circulant graphs for , revealing the structural impact of edge subdivisions on these graph families.
Introduction: Leonhard Euler’s solution to the Seven Bridges of Königsberg problem in 1736 laid the foundation for graph theory, now a major branch of mathematics. Domination in graphs, introduced by Haynes, studies subsets of vertices that can control a graph's behavior. A dominating set (DS) ensures every vertex outside the set is adjacent to at least one vertex in it, with the smallest such set called the domination number . Caro et al. introduced “fair domination,” where a fair dominating set (FDS) ensures equal domination of vertices outside the set. The minimum size of an FDS is the fair domination number . Arumugam and Joseph extended domination concepts with the subdivision number , the minimum edge subdivisions needed to alter a graph's domination properties. Similarly, the fair domination subdivision number (or ) tracks subdivisions to increase or decrease . These concepts have significant theoretical and practical applications, especially in network design and algorithm development. This paper investigates the impact of subdivision on fair domination in cyclic structures. It analyzes how subdivisions influence the properties of fair dominating sets. The study provides insights into structural changes and their effects on fair domination.
Objectives: The Fair Domination Subdivision Number (FDSN) is a graph theory parameter that examines domination properties by assessing how efficiently a set of vertices can exert control over an entire graph. This metric introduces a novel twist by allowing strategic subdivision of specific edges, enabling adjustments to the network structure. Its objective is to highlight the minimum modifications required to enhance the influence of certain nodes while ensuring equitable information spread. In practical applications, FDSN provides valuable insights into social networks and telecommunications, optimizing resource distribution and ensuring consistent service quality across regions. The fair domination criterion requires that each vertex not in the dominating set be adjacent to exactly one vertex in the set, promoting balanced influence. This unique approach balances control and influence within a graph through structural modifications, making it a useful tool for network design and decision-making. Determining FDSN introduces new challenges and dimensions to traditional graph theory, emphasizing fairness, efficiency, and reliability
Results: Fair domination, first introduced by Caro et al., has attracted increasing attention from researchers. In this paper, we provide new insights into the fair domination subdivision number and present valuable theorems along with their proof.
Conclusions: The fair domination subdivision number, a concept in graph theory, holds significant implications for network design and optimization. By determining the minimum number of edge subdivisions required for a fair domination set, this parameter offers insights into the resilience and efficiency of communication networks, social structures, and various other systems modeled as graphs. Understanding this number enables the development of strategies to enhance network robustness, reduce vulnerability to failures, and improve resource allocation, contributing to more resilient and equitable network architectures.