Identifying Codes in the Complementary Prism of Cycles
Márcia Rodrigues Cappelle, Erika M. M. Coelho, Hebert Coelho, Lúcia Draque Penso, Dieter Rautenbach · Electronic Notes in Theoretical Computer Science · 2019
We show that an identifying code of minimum order in the complementary prism of a cycle of order n has order 7 n/ 9 + Θ(1). Furthermore, we observe that the clique-width of the complementary prism of a graph of clique-width k is at most 4 k , and discuss some algorithmic consequences.