Identifying Codes in the Complementary Prism of Cycles

DOI10.1016/J.ENTCS.2019.08.022MaRDI QIDQ6263709arXivWikidataFDO

Authors Márcia R. Cappelle, Erika M. M. Coelho, Hebert Coelho, Lucia Draque Penso, Dieter Rautenbach

Publication date 17 July 2015

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ENTCS.2019.08.022

Mathematics Subject Classification ID

Graph theory (05Cxx) Mathematical programming (90Cxx)

arXiv classification

math.CO

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.

This page was built for publication: Identifying Codes in the Complementary Prism of Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6263709)