پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 42 |
| تعداد شماره‌ها | 1,537 |
| تعداد مقالات | 12,642 |
| تعداد مشاهده مقاله | 26,051,568 |
| تعداد دریافت فایل اصل مقاله | 10,700,735 |
The identifying code number and Mycielski's construction of graphs | ||
| Transactions on Combinatorics | ||
| مقاله 2، دوره 11، شماره 4، اسفند 2022، صفحه 309-316 اصل مقاله (456.81 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2021.126368.1794 | ||
| نویسندگان | ||
| Athena Shaminejad* ؛ Ebrahim Vatandoost؛ Kamran Mirasheh | ||
| Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran | ||
| چکیده | ||
| Let $G=(V, E)$ be a simple graph. A set $C$ of vertices $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).$ Two vertices $x$ and $y$ are twins when $N_{G}[x]=N_{G}[y].$ Graphs with at least two twin vertices are not an identifiable graph. In this paper, we deal with the identifying code number of Mycielski's construction of graph $G.$ We prove that the Mycielski's construction of every graph $G$ of order $n \geq 2,$ is an identifiable graph. Also, we present two upper bounds for the identifying code number of Mycielski's construction $G,$ such that these two bounds are sharp. Finally, we show that Foucaud et al.'s conjecture is holding for Mycielski's construction of some graphs. | ||
| کلیدواژه‌ها | ||
| Dominating Set؛ Identifying Code؛ Mycielski's Construction؛ Identifiable Graph | ||
| مراجع | ||
|
[1] D. Auger, Minimal identifying codes in trees and planar graphs with large girth, European J. Combin., 31 no. 5 (2010) 1372–1384. [2] C. Chen, C. Lu and Z. Miao, Identifying codes and locating-dominating sets on paths and cycles, Discrete Appl. Math., 159 no. 15 (2011) 1540–1547. [3] N. Fazlollahi, D. Starobinski and A. Trachtenberg, Connected identifying codes for sensor network monitoring, In 2011 IEEE Wireless Communications and Networking Conference, (2011) 1026–1031. [4] F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, European J. Combin., 32 no. 4 (2011) 628–638. [5] F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math., 160 no. 10-11 (2010) 1532–1546. [6] A. Frieze, R. Martin, J. Moncel, M. Ruszinkó and C. Smyth, Codes identifying sets of vertices in random networks, Discrete Math., 307 no. 9-10 (2007) 1094–1107. [7] A. N. Ghameshlou, A. Shaminezhad, E. Vatandoost and A. Khodkar, Signed domination and Mycielski’s structure in graphs, RAIRO Oper. Res., 54 no. 4 (2020) 1077–1086. [8] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin., 27 no. 5 (2006) 767–776.
[9] I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput., 33 no. 2 (2004) 304–312. [10] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44 no. 2 (1998) 599–611. [11] A. P. Kazemi, k-tuple total domination and Mycieleskian graphs, Trans. Comb., 1 no. 1 (2010) 7–13.
[12] D. A. Mojdeh and N. Jafari Rad, On domination and its forcing in Mycielski’s graphs, Sci. Iran., 15 no. 2 (2008) 218–222. [13] J. Myscielski, Sur le coloriage des graphes, Colloq. Math., 3 (1955) 161–162.
[14] 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 (ICDM 2006), Bangalore, (2006). | ||
|
آمار تعداد مشاهده مقاله: 465 تعداد دریافت فایل اصل مقاله: 508 |
||