DOMINATION NUMBER AND IDENTIFYING CODE NUMBER OF THE SUBDIVISION GRAPHS

‎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‎.

DOMINATION NUMBER AND IDENTIFYING CODE NUMBER OF THE SUBDIVISION GRAPHS Keywords:

Identifying code‎ , ‎Identifying code number‎ , ‎Subdivision‎ , ‎Domination‎