← Back to Volume 46, Issue 2 Contents
ALGORITHMIC APPROACH FOR SPLIT DOMINATION NUMBER OF GRAPH
Shaikh Jamir Salim1, Pranjali Kekre2
1 Department of Mathematics, Medi Caps University, Indore, Madhya Pradesh, India
2 Department of Mathematics, Medi Caps University, Indore, Madhya Pradesh, India
Volume: 46Issue: 2Pages: 117–131Year: 2024ISSN: 0970-5120
⬇ Download Full PDF
Abstract
This article presents a novel algorithm for determining the split domination number of various graph classes such as Cartesian product of Complete graph and Path graph, its Line graph, Tadpole graph, Line graph of Tadpole graph, web graph and its dual graph etc. To enable the functioning of algorithm, the vertices of these graphs are divided into sets resembling some specific graph types such as $K_1$, $K_2$, $K_{1,2}$, $K_{1,3}$ etc.. By examining these divisions, the algorithm ascertains the bare minimum of vertices required to dominate every other vertex, thereby disconnecting the graph upon removal. This process, known as split domination, is crucial in understanding the connectivity and the structure of graph. The algorithm is versatile and can be applied to any graph that allows for partitioning vertices in the similar fashion.
Keywords: Partitions, Domination Number, Split Domination Number, Split Adjacency Matrix.
MSC 2020: 05C69, 05C85, 05C90, 68R10
How to Cite
Shaikh Jamir Salim, Pranjali Kekre, ALGORITHMIC APPROACH FOR SPLIT DOMINATION NUMBER OF GRAPH, Journal of the Indian Academy of Mathematics, 46(2) (2024), 117–131.
References
- T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (1988): Fundamentals of Domination in Graphs. Marcel Dekker, Inc. New York https://doi.org/10.1201/9781482246582
- Kulli, V. R. and Janakiram, B. (1997): The split domination number of a graph, Graph Theory Notes of New York, XXXII pp. 16-19.
- Beineke, L. W. and Bagga, J. S. (2021): Fundamentals of Line Graphs, In: Line Graphs and Line Digraphs, Developments in Mathematics, Vol. 68, Springer, Cham.
- Beineke, L. W. and Wilson, R. J. (Eds.) (2004): Topics in Algebraic Graph Theory. New York, Cambridge University Press, p. 104.
- S. Maheswari, and S. Meenakshi (2017): Split Domination Number of Some Special Graphs, International Journal of Pure and Applied Mathematics, Vol. 116 (24), pp. 103-117.
- Jamir Shaikh, and Pranjali kekre (2024): Split domination number of some generalized graph's line Graph, Indian J. Nat. Sci., Issue 83.
- Fayed F. M Ghaleb, and Ramy S. Shaheen, (2002): Algorithms for finding a dominating set and the domination number of toroidal grid graphs, Journal of Applied Mathematics, International, Vol. 8.
- James K. Lan, and Gerard Jennhwa Chang, (2013): Algorithmic aspects of the kdomination problem in graphs, Discrete Applied Mathematics, Volume 161, Issues 10-11, pp. 1513-1520.
- Narsing Deo (1974): Graph Theory with Applications to Engineering and Computer Science, Dover Publications, Inc. Mineola, New York.
- Jamir Shaikh and Pranjali kekre (2024): Split domination number of dual graph of generalized form of specified graphs, Journal of the Calcutta Mathematical Society, Vol. 20 (1), pp. 11-26.
© Journal of the Indian Academy of Mathematics