Algorithm Using LPP for Domination and Fractional Domination Number of Some Graphs - Sarada, Mahesh; Jain, Rekha; Mundhe, Ganesh (Communications in Mathematics and Applications, 2024)
In the given study to find the connected graph’s domination number and fractional domination number we have used Linear Programming Problem (LPP) formulation. We have design an algorithm using LPP formulation and linear programming solver to obtain the smallest size of dominating set for cycle graph, complete graph, wheel graph, bipartite graph, tree graph, n-connected graph. The basic steps of the simplex method for solving a minimization and maximization LPP problem. Generalized algorithm to find fractional domination number of any graph. The fractional domination number of a graph has a wide range of applications in graph theory and related fields, and it is an important parameter to consider when analysing and designing networks and algorithms.
Keywords: Dominating set; Fractional domination number; LPP formulation; Algorithm