The identifying code number and Mycielski's construction of graphs

Abstract

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.

Keywords

• dominating set
• identifying code
• mycielski's construction
• identifiable graph