identifying code

Let $R$ be a commutative ring with identity, and $ \mathrm{A}(R) $ be the set of ideals with non-zero annihilator. The annihilating-ideal graph of $ R $ is defined as the graph $AG(R)$ with the vertex set $ \mathrm{A}(R)^{*}=\mathrm{A}(R)\setminus\lbrace 0\rbrace $ and two distinct vertices $ I $ and $ J $ are adjacent if and only if $ IJ=0 $. In this paper, we characterize all positive integers $n$ for which $AG(\mathbb{Z}_n)$ is identifiable.

Let $\Gamma=(V, E)$ be a simple graph. A set $C$ of vertices $\Gamma$ is an identifying set of $\Gamma$ if for every two vertices $x$ and $y$ the sets $N_{\Gamma}[x] \cap C$ and $N_{\Gamma}[y] \cap C$ are non-empty and different. Given a graph $\Gamma,$ the smallest size of an identifying set of $\Gamma$ is called the identifying code number of $\Gamma$ and is denoted by $\gamma^{ID}(\Gamma).$ Two vertices $x$ and $y$ are twins when $N_{\Gamma}[x]=N_{\Gamma}[y].$ Graphs with at least two twin vertices are not identifiable graph. In this paper, we study identifying code number of some Cayley graphs.

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 NG[x] ∩ C and NG[y] ∩ 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 γ ID(G). Two vertices x and y are twins when NG[x] = NG[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 ≥ 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.

* Formulas are not displayed correctly.