Algorithm Using LPP for Domination and Fractional Domination Number of Some Graphs

Authors

DOI:

https://doi.org/10.26713/cma.v15i5.2840

Keywords:

Dominating set, Fractional domination number, LPP formulation, Algorithm

Abstract

 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.

Downloads

Download data is not yet available.

References

V. A. Alfred, E. H. John and D. U. Jeffrey, The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, x + 470 pages (1974).

M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-Domination and k-independence in graphs: A survey, Graphs and Combinatorics 28 (2012), 1 – 55, DOI: 10.1007/s00373-011-1040-3.

E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10(3) (1980), 211 – 219, DOI: 10.1002/net.3230100304.

G. S. Domke, S. T. Hedetniemi and R. C. Laskar, Fractional packing, coverings and irredundance in graphs, Congressus Numerantium 66 (1988), 227 – 238.

J. F. Fink and M. S. Jacobson, n-Domination in graphs, in: Graph Theory with Application to Algorithms and Computer Science, John Wiley and Sons, New York, pp. 283–300 (1985).

D. C. Fisher, Fractional dominations and fractional total dominations of graph complements, Discrete Applied Mathematics 122 (1-3) (2002), 283 – 291, DOI: 10.1016/s0166-218x(01)00305-5.

G. H. Fricke, M. A. Henning, O. R. Oellermann and C. S. Henda, An algorithm to find two distance domination parameters in a graph, Discrete Applied Mathematics 68(1-2) (1996), 85 – 91, DOI: 10.1016/0166-218x(95)00057-x.

F. Harary, Graph Theory, Addison-Wesley Publishing Company Inc., ix + 274 pages (1969).

T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Topics in Domination in Graphs, Springer Cham., viii + 545 pages (2020), DOI: 10.1007/978-3-030-51117-3.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, 1st edition, CRC Press, Boca Raton, 464 pages (1998), DOI: 10.1201/9781482246582.

J. K. Lan and G. J. Chang, Algorithmic aspects of the k-domination problem in graphs, Discrete Applied Mathematics 161(10-11) (2013), 1513 – 1520, DOI: 10.1016/j.dam.2013.01.015.

H. B. Merouane and C. Mustapha, An algorithm for the dominator chromatic number of a tree, Journal of Combinatory Optimization 30 (2015), 27 – 33, DOI: 10.1007/s10878-013-9631-y.

M. Sarada, R. Jain and G. Mundhe, Applications of the domination and fractional domination in computational biology using LPP formulation, African Journal of Biological Sciences 6(5) (2024), 4340 – 4358.

M. Sarada, R. Jain and G. Mundhe, Relation between the fractional domination number of some graphs and their line graphs, Communications on Applied Nonlinear Analysis 31(6s) (2024), 670 – 691, DOI: 10.52783/cana.v31.1260.

Downloads

Published

31-12-2024
CITATION

How to Cite

Sarada, M., Jain, R., & Mundhe, G. (2024). Algorithm Using LPP for Domination and Fractional Domination Number of Some Graphs. Communications in Mathematics and Applications, 15(5), 1541–1560. https://doi.org/10.26713/cma.v15i5.2840

Issue

Vol. 15 No. 5 (2024)

Section

Research Article

License

Creative Commons Licence 4.0 by  

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.