Malaysian Journal of Mathematical Sciences, December 2025, Vol. 19, No. 4
Identification Number of Antiprism Graphs
Tolentino, M. A. C.
Corresponding Email: mtolentino@ateneo.edu
Received date: 15 January 2025
Accepted date: 3 July 2025
Abstract:
Let $G$ be a simple, connected, undirected, nontrivial graph and let $c$ be a coloring of the vertices of $G$ using the colors red and white such that not all the vertices are colored white. For each vertex $v$ of $G$, we can assign a vector code $\vec{d}(v)=(a_1,a_2,\ldots,a_{\text{diam}(G)} )$, where $\text{diam}(G)$ is the diameter of $G$ and, for each $i=1,2,\ldots,\text{diam}(G)$, the component $a_i$ is equal to the number of red vertices whose distance to $v$ is $i$. Then, $c$ is said to be an ID-coloring of $G$ if $\vec{d}(v) \neq \vec{d}(w)$ for any pair of distinct vertices $v$ and $w$. If $G$ has an identification coloring, it is called an ID-graph and its identification number $ID(G)$ is defined to be the least number of red vertices needed to construct an ID-coloring of $G$. An ID-coloring of $G$ can be used to distinguish its vertices from each other and this is particularly interesting when $G$ has nontrivial automorphisms. Indeed, identification colorings have been studied for paths, cycles, grids, prisms, and some tree families, including caterpillar and lobster graphs. In this paper, we consider identification colorings for antiprism graphs, which have not been previously studied in relation to this topic. An antiprism graph is a graph that corresponds to the skeleton of an antiprism. Antiprism graphs are known to be vertex-transitive; thus, they possess nontrivial automorphisms. Our results include a characterization of all ID-antiprisms and the determination of the identification number of any ID-antiprism.
Keywords: identification coloring; multiset resolving set; antiprism graphs
