TY - JOUR
ID - 26088
TI - The identifying code number and Mycielski's construction of graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Shaminejad, Athena
AU - Vatandoost, Ebrahim
AU - Mirasheh, Kamran
AD - Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran
Y1 - 2022
PY - 2022
VL - 11
IS - 4
SP - 309
EP - 316
KW - dominating set
KW - Identifying code
KW - Mycielski's Construction
KW - Identifiable Graph
DO - 10.22108/toc.2021.126368.1794
N2 - 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.
UR - https://toc.ui.ac.ir/article_26088.html
L1 - https://toc.ui.ac.ir/article_26088_858b032cc710d026f084d95cbe679621.pdf
ER -