Independent transversal domination subdivision number of trees

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, D.B. Jain College, Chennai 600 097, Tamil Nadu, India

2 Department of Mathematics, S.D.N.B. Vaishnav College for Women, Chennai 600 044, Tamil Nadu, India

Abstract

A set $S\subseteq V $ of vertices in a graph $G=(V,E)$ is called a dominating set if every vertex in $V \setminus S $ is adjacent to a vertex in S. The domination number $\gamma(G)$ is the minimum cardinality of a dominating set of $G$. The domination subdivision number $sd_{\gamma}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the domination number. Sahul Hamid  defined a dominating set which intersects every maximum independent set in $G$ to be an \textit{independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number} of $G$ and is denoted by $\gamma_{it}(G)$. We extend the idea of domination subdivision number  to independent transversal domination.  The independent transversal domination subdivision number of a graph $G$ denoted by $sd_{\gamma_{it}}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the independent transversal domination number. In this paper we initiate a study of this parameter with respect to trees.

Keywords

Main Subjects

References

[1] S.E. Anderson and K. Kuenzel, Independent transversal domination in trees, products and under local changes to a graph, Aequationes Math. 96 (2022), no. 5, 981–995.
https://doi.org/10.1007/s00010-022-00896-0
[2] H. Aram, S.M. Sheikholeslami, and O. Favaron, Domination subdivision numbers of trees, Discrete Math. 309 (2009), no. 4, 622–628.
https://doi.org/10.1016/j.disc.2007.12.085
[3] G. Chartrand and L. Lesniak, Graphs and Digraphs, Fourth Edition, CRC press, Boca Raton, 2005.
[4] I.S. Hamid, Independent transversal domination in graphs, Discuss. Math. Graph Theory 32 (2012), no. 1, 5–17.
[5] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of domination in graphs, CRC press, 2013.
[6] A.C. Martínez, J.M.S. Almira, and I.G. Yero, On the independence transversal total domination number of graphs, Discrete Appl. Math. 219 (2017), 65–73.
https://doi.org/10.1016/j.dam.2016.10.033
[7] P.R.L. Pushpam and K.P. Bhanthavi, The stability of independent transversal domination in trees, Discrete Math. Algorithms Appl. 13 (2021), no. 1, Article ID: 2050097.
https://doi.org/10.1142/S1793830920500974
[8] D.S. Sevilleno and F.P. Jamil, On independent transversal dominating sets in graphs, Eur. J. Pure Appl. 14 (2021), no. 1, 149–163.
https://doi.org/10.29020/nybg.ejpam.v14i1.3904
[9] S. Velammal and S. Arumugam, Domination and subdivision in graphs, Indian J. Appl. Res. 1 (2011), no. 3, 180–183.
[10] H. Wang, B. Wu, and X. An, Independent transversal domination number of a graph, arXiv preprint arXiv:1704.06093 (2017).
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 August 2024

Files

Share

How to cite

Statistics