Authors:
G. Navamani,Reena Mercy M. A.,A. Josephine Christilda,Dharmaraj Mohankumar,DOI NO:
https://doi.org/10.26782/jmcms.2025.12.00003Keywords:
Influence-based vertex covering,Uniform vertex influence,k-regular fair domination,Edge-splitting parameter,Subdivision for fair domination,Abstract
This study explores a specialized type of domination in graphs known as fair domination. A fair dominating set (FDS) in a graph R is defined as a dominating set in which every non-member vertex is adjacent to an equal number of vertices within the set. The minimum size of such a set is referred to as the fair domination number, denoted γ_fd (R). We further examine how structural modifications, specifically edge subdivisions, affect this parameter. The fair domination subdivision number, denoted 〖Sd〗_(γ_fd)^+ (R) (or 〖Sd〗_(γ_fd)^- (R)), captures the smallest number of edge subdivisions required to increase or decrease the fair domination number, respectively. Our work focuses on computing these values for two graph families: cycles C_n (with n≥3) and Circulant graphs C_n (1,k),k=2,3. Through detailed analysis, we demonstrate how edge subdivisions impact the fairness condition in domination. To systematically explore fair domination in graphs, we adopt an algorithmic approach that facilitates efficient identification of fair dominating sets and computation of related parameters. Algorithmic techniques have been pivotal in graph theory, particularly in the study of domination-related problems. We introduce an efficient algorithm for identifying fair dominating sets and determining the fair domination number in Circulant graphs of the form〖 C〗_n(1,2) and C_n (1,3), offering insights into their underlying combinatorial structure.Refference:
I. Blažej, Václav, Jan Matyáš Křišťan, and Tomáš Valla: ‘Computing m-eternal domination number of cactus graphs in linear time’. arXiv. arXiv:2301.05155, 2023. https://doi.org/10.48550/arXiv.2301.05155.
II. Boehmer, Niclas, Tomohiro Koana, and Rolf Niedermeier: ‘A refined complexity analysis of fair districting over graphs.’ Autonomous Agents and Multi-Agent Systems. Vol. 37(1), pp: 13, 2023. 10.48550/arXiv.2102.11864.
III. Caro, Yair, Adriana Hansberg, and Michael Henning: ‘Fair domination in graphs’. Discrete Mathematics. Vol. 312(19), pp: 2905-2914, 2012. 10.1016/j.disc.2012.05.006.
IV. Casado, Alejandra, Jesús Sánchez-Oro, and Anna Martínez-Gavara: ‘Heuristics for the weighted total domination problem’. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research. Vol. 33(2), pp: 395–436, 2025 10.1007/s11750-025-00695-1.
V. Dejter, Italo J: ‘Perfect domination in regular grid graphs’. Australasian Journal of Combinatoricsz. Vol. 42, pp: 99–114, 2007. 10.48550/arXiv.0711.4343.
VI. Enriquez, Enrico, et al : ‘Domination in fuzzy directed graphs’. Mathematics. Vol. 9(17), pp: 2143, 2021. 10.3390/math9172143.
VII. Hajian, Majid, and N. Jafari Rad: ‘Trees and unicyclic graphs with large fair domination number’. Util. Math. Vol. 112, 2022.
VIII. Hajian, Majid, and Nader Jafari Rad: ‘Fair domination number in cactus graphs’. Discussiones Mathematicae Graph Theory. Vol. 39(2), pp: 489-503, 2019.
IX. Hansberg, Adriana: ‘Reviewing some results on fair domination in graphs’. Electronic Notes in Discrete Mathematics. Vol. 43, pp: 367-373, 2013. https://doi.org/10.1016/j.endm.2013.07.054.
X. Harary, Frank. Graph theory (on Demand Printing of 02787). CRC Press, 2018. 10.1201/9780429493768.
XI. Hatami, Hamed, and Pooya Hatami: ‘Perfect dominating sets in the Cartesian products of prime cycles’. The Electronic Journal of Combinatorics, Vol. 14(1), pp: N8, 2007. https://doi.org/10.37236/1009.
XII. Haynes, Teresa W., Stephen Hedetniemi, and Peter Slater: ‘Fundamentals of domination in graphs’. CRC press, 2013. 10.1201/9781482246582.
XIII. Henning, Michael A., Arti Pandey, and Vikash Tripathi: ‘Complexity and algorithms for semipaired domination in graphs’. Theory of Computing Systems, Vol. 64(7), pp: 1225-1241, 2020. 10.48550/arXiv.1904.00964.
XIV. Inza, Ernesto Parra, et al: ‘Algorithms for the global domination problem’. Computers & Operations Research. Vol. 173, pp: 106876, 2025. 10.1016/j.cor.2024.106876.
XV. Jafari Rad, Nader, et al: ‘Total domination in cubic Knödel graphs’. Communications in Combinatorics and Optimization. Vol. 6(2), pp: 221-230, 2021. 10.22049/cco.2020.26793.1143.
XVI. Joseph, J. Paulraj, and S. Arumugam: ‘Domination in subdivision graphs’. J. Indian Math. Soc. Vol. 62, pp: 274-282, 1996.
XVII. Kumar, J. Pavan, and P. Venkata Subba Reddy: ‘Algorithmic aspects of some variants of domination in graphs’. Analele Stiint. Ale Univ. Ovidius Constanta Ser. Mat. Vol. 28(3), pp: 153-170, 2020. 10.48550/arXiv.2002.00002.
XVIII. Kumar, J. Pavan, P. Venkata Subba Reddy, and S. Arumugam: ‘Algorithmic complexity of secure connected domination in graphs’. AKCE International Journal of Graphs and Combinatorics. Vol. 17(3), pp: 1010-1013, 2020. 10.48550/arXiv.2002.00002.
XIX. Lin, Ching-Chi, Cheng-Yu Hsieh, and Ta-Yu Mu: ‘A linear-time algorithm for weighted paired-domination on block graphs’. Journal of Combinatorial Optimization. Vol. 44(1), pp: 269-286, 2022. 10.1007/s10878-021-00767-5.
XX. Miranda, Aldwin T., and Rolito G. Eballe : ‘Domination defect for the join and corona of graphs’. Applied Mathematical Sciences. Vol. 15(12), pp: 615-623, 2021. 10.12988/ams.2021.914597.
XXI. Mu, Ta-Yu, and Ching-Chi Lin: ‘Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs’. arXiv. arXiv:2411.19476, 2024. 10.48550/arXiv.2411.19476.
XXII. Navamani. G and Reena Mercy M A: ‘Fair domination number of some graphs’. Preprint.
XXIII. Novak, Tina, and Janez Žerovnik: ‘A Linear Time Algorithm for Weighted k-Fair Domination Problem in Cactus Graphs’. Operations Research Forum Cham: Springer International Publishing. Vol. 3(3), 2022. 10.1007/s43069-022-00154-8.
XXIV. Pushpam, P. Roushini Leely, and G. Navamani: ‘Eternal m-security in certain classes of graphs’. J. Combin. Math. Combin. Vol. 92, pp: 25-38, 2015.
XXV. Rad, Nader Jafari: ‘Domination in circulant graphs’. Analele Stiintifice Ale Universitatii Ovidius Constanta, Seria Matematica. Vol. 17(1), pp: 169-176, 2019.
XXVI. Swaminathan, V., et al: ‘Outer complete fair domination in graphs’. Discrete Mathematics, Algorithms and Applications. Vol. 14(03), pp: 2150126, 2022. 10.1142/S1793830921501263.