Independent location-domination number of graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok, Thailand

2 Mathematics and Statistics with Applications (MaSA), Bangkok, Thailand

3 Department of Mathematics, St Joseph’s University, Bengaluru, India

Abstract

Let $G = (V(G), E(G))$ be a graph. A set $I \subseteq V(G)$ is independent if no two vertices of $I$ are adjacent. A set $D \subseteq V(G)$ is dominating if every vertex $u \in V(G) \setminus D$ is adjacent to a vertex in $D$. A set $L \subseteq V(G)$ is an independent locating-dominating set (ILD-set) of $G$ if $L$ is independent and dominating with the additional property that $N (u) \cap L \neq N (v) \cap L$ for any pair of distinct $u, v \in V(G) \setminus L$. The independent location-domination number of a graph $G$ is the minimum cardinality of an ILD-set of $G$ and is denoted by $i_{\ell}(G)$. In this paper, we study the non-existence of ILD-sets of maximal outerplanar graphs and circulants graphs. In trees, we prove that \textcolor{red}{$\frac{n + 1}{3} \leq i_{\ell}(T) \leq n - 1$} for every tree $T$ of $n$ vertices. We further prove that there exists a tree $T$ with prescribed value $i_{\ell}(T)$ between these bounds.

Keywords

Main Subjects

References

[1] C. Balbuena, F. Foucaud, and A. Hansberg, Locating-dominating sets and identifying codes in graphs of girth at least 5, Electron. J. Comb. 22 (2015), no. 2, 1–22. https://doi.org/10.37236/4562
[2] M. Blidia, M. Chellali, F. Maffray, Moncel, and A. Semri, Locating-domination and identifying codes in trees, Australas. J. Combin. 39 (2007), 219–232.
[3] N. Bousquet, Q. Deschamps, T. Lehtilä, and A. Parreau, Locating-dominating sets: From graphs to oriented graphs, Discrete Math. 346 (2023), 113124. https://doi.org/10.1016/j.disc.2022.113124
[4] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, and M.L. Puertas, Locating-dominating codes, Appl. Math. Comput. 220 (2013), 38–45. https://doi.org/10.1016/j.amc.2013.05.060
[5] D. I. Carson, On generalized location-domination, Graph Theory, Combinatories and Applications (Y. Alavi and A. Schwenk, eds.), John Wiley and Sons, Inc., New York, 1995, pp. 161–179.
[6] I. Charon, O. Hudry, and A. Lobstein, Possible cardinalities for locating-dominating codes in graphs, Australas. J. Combin. 34 (2006), 23–32.
[7] M. Chellali, M. Mimouni, and P.J. Slater, On locating-domination in graphs, Discuss. Math. Graph Theory 30 (2010), 223–235. https://doi.org/10.7151/dmgt.1488
[8] C.J. Colbourn, P.J. Slater, and L.K. Stewart, Locating-dominating sets in series-parallel networks, Congr. Numer. 56 (1987), 135–162.
[9] A. Finbow and B.L. Hartnell, On locating-dominating sets and well-covered graphs, Congr. Numer. 65 (1988), 191–200.
[10] F. Foucaud, M.A. Henning, C. Löwenstein, and T. Sasse, Locating-dominating sets in twin-free graphs, Discrete Appl. Math. 200 (2016), 52–58. https://doi.org/10.1016/j.dam.2015.06.038
[11] A.K.A. Gafur and A.W. Saputro, On locating-dominating set of regular graphs, J. Math. 2021 (2021), 8147514.
https://doi.org/10.1155/2021/8147514
[12] R.M. Güvens, G. Yu, and R.K. Kincaid, Open locating-dominating sets in circulant graphs, Discuss. Math. Graph Theory 42 (2022), 47–62. https://doi.org/10.7151/dmgt.2235
[13] T.W. Haynes, M.A. Henning, and J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math. 154 (2016), no. 8, 1293–1300. https://doi.org/10.1016/j.dam.2006.01.002
[14] R. Kincaid, A. Oldham, and G. Yu, Optimal open-locating-dominating sets in infinite triangular grids, Discrete Appl. Math. 193 (2015), 139–144. https://doi.org/10.1016/j.dam.2015.04.024
[15] A. Pandey, Open neighborhood locating-dominating set in graphs: Complexity and algorithms, Proc. Int. Conf. on Information Technology (ICIT) (Bhubaneswar, India), 2015, pp. 1–6.
[16] D.F. Rall and P.J. Slater, On location-domination numbers for certain classes of graphs, Congr. Numer. 45 (1984), 97–106.
[17] P.J. Slater, Dominating and location in acyclic graphs, Networks 17 (1987), no. 1, 55–64. https://doi.org/10.1002/net.3230170105
[18] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445–455.
[19] P.J. Slater and J. Sewell, Independent locating-dominating sets and independent identifying codes in graphs, J. Combin. Math. Combin. Comput. 104 (2018), 261–272.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 20 April 2026

Files

Share

How to cite

Statistics