DOMINATION NUMBER AND IDENTIFYING CODE NUMBER OF THE SUBDIVISION GRAPHS

Articles in Press

Document Type : Original Manuscript

Authors

Department of Mathematics, Faculty of Science, Imam Khomeini International University, P.O. Box 3414896818, Qazvin, Iran.

Abstract

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

Keywords

Journal of Algebraic Systems

Articles in Press, Accepted Manuscript
Available Online from 09 April 2024

Files

Share

How to cite

Statistics