Identifying Codes in the Complementary Prism of Cycles

Abstract

We show that an identifying code of minimum order in the complementary prism of a cycle of order $n$ has order $7n/9+\Theta (1)$. Furthermore, we observe that the clique-width of the complementary prism of a graph of clique-width $k$ is at most $4k$, and discuss some algorithmic consequences.