Optimizing Subdivisions on Fair Domination in Petersen Graph Structures

Abstract

A fair dominating set (FDS) J is a dominating set of a graph H, such that all vertices in V \J are dominated by the same number of vertices of J. The fair domination number (FDN) is the minimum cardinality of a fair dominating set of H, denoted by γ_fd (H). The domination subdivision number (FDSN) 〖Sd〗_γ (H), represents the smallest number of edges in H 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, 〖Sd〗_(γ_fd)^+ (H) (or  〖Sd〗_(γ_fd)^- (H))  is the minimum number of edge subdivisions needed to be applied to the graph H to increase (or decrease) the fair domination number of the graph. In this paper, we present the fair domination subdivision numbers for Petersen graphs P(n,k) for k = 1,2, 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 number of elements in the smallest such set called the domination number γ(H) . Caro et al. introduced “fair domination,” where a “fair dominating set (FDS)” J is a DS of a graph H, such that all vertices in V \J are dominated by the same number of vertices from J. The minimum size of an FDS is the fair domination number γ_fd (H). Arumugam and Joseph extended domination concepts with the subdivision number 〖Sd〗_γ (H), the minimum edge subdivisions needed to alter a graph's domination properties. Similarly, the fair domination subdivision number 〖Sd〗_(γ_fd)^+ (H) (or  〖Sd〗_(γ_fd)^- (H)) tracks subdivisions to increase or decrease γ_fd (H). These concepts have significant theoretical and practical applications, especially in network design and algorithm development.
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, initially introduced by Caro et al., has garnered growing interest from researchers. In this paper, we present new insights into the fair domination subdivision number, and useful new theorems with proof.
Conclusions: The fair domination subdivision number, a key concept in graph theory, has important implications for optimizing network design. By identifying the minimum number of edge subdivisions needed for a fair domination set, this parameter provides insights into the resilience and efficiency of communication networks, social systems, and other graph-modelled structures. Understanding this metric enables the formulation of strategies to bolster network robustness, decrease susceptibility to failures, and enhance resource distribution, ultimately supporting the development of more resilient and equitable network architectures.