Certified Total Secure Domination in Marketing Graph Networks of Multi-Branch Coaching Institutes: A Graph-Theoretic Framework for Student Attraction and Brand Propagation
DOI:
https://doi.org/10.70917/ijcisim-2026-5048Keywords:
Digital finance; Entropy weight method; Coupling and coordination; Grey relational degree; Regional differentiationAbstract
Let be a finite, simple and undirected graph. In the proposed marketing-network model, each vertex is a branch, centre, digital hub, admission office, or flagship unit of a brand-uniform coaching institute, and each edge records a relevant intra-brand communication, referral, administrative, or catchment-proximity relation. Motivated by secure domination in graph protection and by the need for auditable branch responsibility, this paper introduces the certified total secure dominating set. A set is certified total secure if it is a total dominating set, a secure dominating set, and each vertex either has an external private neighbour with respect to or satisfies . The corresponding invariant is denoted by . The certification rule used here is deliberately separated from the classical certified domination condition of Dettlaff et al.; it is a private-territory certification rule adapted to branch-network design. Exact values of are obtained for paths, cycles, stars, complete graphs, complete bipartite graphs, and wheels. A strict branch-fibre version is also solved for rectangular grid networks. Valid general bounds, an exact-verification subroutine, a greedy feasible-set algorithm, and a coaching-network interpretation are supplied.
Keywords: domination in graphs; secure domination; total domination; certified domination; private neighbour; graph protection; coaching institute networks; educational marketing.
Downloads
References
References
C. Berge, Theory of Graphs and its Applications, Methuen, London, 1962.
O. Ore, Theory of Graphs, American Mathematical Society Colloquium Publications, Vol. 38, Providence, 1962.
E. J. Cockayne and S. T. Hedetniemi, “Towards a theory of domination in graphs,” Networks, 7(3), 247–261, 1977. doi: 10.1002/net.3230070305.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, “Total domination in graphs,” Networks, 10(3), 211–219, 1980. doi: 10.1002/net.3230100304.
M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013. doi: 10.1007/978-1-4614-6525-6.
E. J. Cockayne, P. J. P. Grobler, W. R. Grundlingh, J. Munganga and J. H. van Vuuren, “Protection of a graph,” Utilitas Mathematica, 67, 19–32, 2005.
S. Benecke, E. J. Cockayne and C. M. Mynhardt, “Secure total domination in graphs,” Utilitas Mathematica, 74, 247–259, 2007.
W. F. Klostermeyer and C. M. Mynhardt, “Secure domination and secure total domination in graphs,” Discussiones Mathematicae Graph Theory, 28(2), 267–284, 2008. doi: 10.7151/dmgt.1405.
M. Dettlaff, M. Lemanska, J. Topp, R. Ziemann and P. Zylinski, “Certified domination,” AKCE International Journal of Graphs and Combinatorics, 17(1), 86–97, 2020. doi: 10.1016/j.akcej.2018.09.004.
M. Dettlaff, M. Lemanska, M. Miotk, J. Topp, R. Ziemann and P. Zylinski, “Graphs with equal domination and certified domination numbers,” Opuscula Mathematica, 39(6), 815–827, 2019. doi: 10.7494/OpMath.2019.39.6.815.
P. K. Jakkepalli, S. Arumugam, H. Khandelwal and V. S. R. P., “Algorithmic aspects of certified domination in graphs,” Communications in Combinatorics and Optimization, 7(2), 247–255, 2022. doi: 10.22049/cco.2021.27302.1226.
A. Cabrera Martinez, L. P. Montejano and J. A. Rodriguez-Velazquez, “On the secure total domination number of graphs,” Symmetry, 11(9), Article 1165, 2019. doi: 10.3390/sym11091165.
A. Cabrera Martinez, A. Estrada-Moreno and J. A. Rodriguez-Velazquez, “Secure total domination in rooted product graphs,” Mathematics, 8(4), Article 600, 2020. doi: 10.3390/math8040600.
Y. Aita and T. Araki, “Secure total domination number in maximal outerplanar graphs,” Discrete Applied Mathematics, 348, 221–229, 2024. doi: 10.1016/j.dam.2024.04.007.
T. Alsuraiheed, J. A. Mercy, L. B. M. Raj and T. Asir, “On the strong secure domination number of a graph,” Mathematics, 12(11), Article 1666, 2024. doi: 10.3390/math12111666.
J. Raczek and M. Miotk, “Theoretical modelling of efficient fire safety water networks by certified domination,” Scientific Reports, 14, Article 21574, 2024. doi: 10.1038/s41598-024-72285-3.
J. Raczek and M. Miotk, “Two approaches to constructing certified dominating sets in social networks,” IEEE Access, 13, 17495–17505, 2025. doi: 10.1109/ACCESS.2025.3532392.
Central Consumer Protection Authority, Government of India, Guidelines for Prevention of Misleading Advertisement in Coaching Sector, Press Information Bureau, 13 November 2024.
IMARC Group, India Coaching Institutes Market Size, Industry Report 2034, 2025.
