Optimal Adjacency Labels for Subgraphs of Cartesian Products

MaRDI QIDQ6401292zbMATH OpenFDO

Authors L. Esperet, Nathaniel Harms, Victor Zamaraev

Publication date 6 June 2022

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph theory (including graph drawing) in computer science (68R10)

Abstract: For any hereditary graph class $mathcalF$, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $mathcalF$. As a consequence, we show that, if $mathcalF$ admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $mathcalF$ do too.

This page was built for publication: Optimal Adjacency Labels for Subgraphs of Cartesian Products

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