Identification Number of Antiprism Graphs

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 d⃗ (v)=(a1,a2,…,adiam(G)) , where diam(G) is the diameter of G and, for each i=1,2,…,diam(G) , the component ai 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 d⃗ (v)≠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.