آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,578 |
| تعداد مشاهده مقاله | 1,707,519 |
| تعداد دریافت فایل اصل مقاله | 1,590,793 |
Independent location-domination number of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 12، دوره 11، شماره 4، اسفند 2026، صفحه 1197-1213 اصل مقاله (812.51 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30238.2378 | ||
| نویسندگان | ||
| Pailin Kaewperm1، 2؛ David A. Kalarkop3؛ Pawaton Kaemawichanurat* 1، 2 | ||
| 1Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok, Thailand | ||
| 2Mathematics and Statistics with Applications (MaSA), Bangkok, Thailand | ||
| 3Department of Mathematics, St Joseph’s University, Bengaluru, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| independence number؛ domination number؛ location-domination | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 178 تعداد دریافت فایل اصل مقاله: 148 |
||