DOMINATION NUMBER AND IDENTIFYING CODE NUMBER OF THE SUBDIVISION GRAPHS | ||
| Journal of Algebraic Systems | ||
| مقاله 1، دوره 13، شماره 2، مهر 2025، صفحه 1-11 اصل مقاله (145.36 K) | ||
| نوع مقاله: Original Manuscript | ||
| شناسه دیجیتال (DOI): 10.22044/jas.2023.12257.1649 | ||
| نویسندگان | ||
| Somaiya Ahmadi1؛ Ebrahim Vatandoost2؛ Ali Behtoei* 2 | ||
| 1Department of Mathematics, Faculty of Science, Imam Khomeini International University, P.O. Box 3414896818, Qazvin, Iran | ||
| 2Department of Mathematics, Faculty of Science, Imam Khomeini International University, P.O. Box 3414896818, Qazvin, Iran. | ||
| چکیده | ||
| Let $G=(V, E)$ be a simple graph. A set $C$ of vertices of $G$ is an identifying code of $G$ if for every two vertices $x$ and $y$ the sets $N_{G}[x] \cap C$ and $N_{G}[y] \cap C$ are non-empty and different. Given a graph $G,$ the smallest size of an identifying code of $G$ is called the identifying code number of $G$ and denoted by $\gamma^{ID}(G).$ In this paper, we prove that the identifying code number of the subdivision of a graph $G$ of order $n$ is at most $n$. Also, we prove that the identifying code number of the subdivision of graphs $K_n$, $K_{r,s}$ and $C_P(s)$ are $n$, $r+s$ and $2s$, respectively. Finally, we conjecture that for every graph $G$ of order $n$ the identifying code number of the subdivision of $G$ is $n$. | ||
| کلیدواژهها | ||
| Identifying code؛ Identifying code number؛ Subdivision؛ Domination | ||
| مراجع | ||
|
1. J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin., 69 (2017), 271–285.
2. D. Auger, I. Charon, O. Hudry and A. Lobstein, Watching systems in graphs: an extension of identifying codes, Discret. Appl. Math., 161 (2013), 1674–1685.
3. D. Auger, Minimal identifying codes in trees and planar graphs with large girth, European J. Combin., 31 (2010), 1372–1384.
4. A. Behtoei, E. Vatandoost and F. Azizi Rajol Abad, Signed Roman domination number and join of graphs, J. Algebr. Syst., 4 (2016), 65–77.
5. C. Chen, C. Lu and Z. Miao, Identifying codes and locating–dominating sets on paths and cycles, Discret. Appl. Math., 159 (2011), 1540–1547.
6. M. Dettlaff, M. Lemańska, M. Miotk, J. Topp, R. Ziemann and P. Z_ yliński, Graphs with equal domination and certified domination numbers, Opuscula Math., 39 (2019), 815–827.
7. N. Fazlollahi, D. Starobinski and A. Trachtenberg, Connected identifying codes for sensor network monitoring, IEEE Wireless Communications and Networking Conference, (2011), 1026–1031.
8. F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discret. Appl. Math., 160 (2012), 1532–1546.
9. A. Frieze, R. Martin, J. Moncel, M. Ruszinkó and C. Smyth, Codes identifying sets of vertices in random networks, Discrete Math., 307 (2007), 1094–1107.
10. S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin., 27 (2006), 767–776.
11. T. Haynes, D. Knisley, E. Seier and Y. Zou, A quantitative analysis of secondary RNA structure using domination-based parameters on trees, BMC bioinform., 7 (2006), 108– 115.
12. M. D. Hernando Martin, M. Mora Giné and I. M. Pelayo Melero, Watching systems in complete bipartite graphs, Jor. de Mat. Disc. Alg., 11 (2012), 53–60.
13. I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput., 33 (2004), 304–312.
14. M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf., 44 (1998), 599–611.
15. Z. Mansouri and D. A. Mojdeh, Outer independent rainbow dominating functions in graphs, Opuscula Math., 40 (2020), 599–615.
16. F. Ramezani, E. D. Rodriguez-Bazan and J. A. Rodriguez-Velazquez, On the Roman domination number of generalized Sierpinski graphs, Filomat, 31 (2017), 6515–6528.
17. A. Shaminejad and E. Vatandoost, The identifying code number and functigraphs, J. Algebr. Syst., 10 (2022), 155–166.
18. A. Shaminezhad and E. Vatandoost, On 2-rainbow domination number of functigraph and its complement, Opuscula Math., 40 (2020), 617–627.
19. B. Stanton, On vertex identifying codes for infinite lattices, PhD Thesis, Iowa State University, 2011, arXiv: 1102.2643.
20. K. Thulasiraman, M. Xu, Y. Xiao and X. D. Hu, Vertex identifying codes for fault isolation in communication networks, In Proceedings of the International Conference on Discrete Mathematics and Applications, Bangalore, 2006.
21. E. Vatandoost and F. Ramezani, On the domination and signed domination numbers of a zero-divisor graph, Electron. J. Graph Theory Appl. (EJGTA), 4 (2016), 148–156. | ||
|
آمار تعداد مشاهده مقاله: 361 تعداد دریافت فایل اصل مقاله: 405 |
||