2026-07-22T16:01:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18109 2024-03-06T11:01:02Z ddc:004 open_access

Optimal Adjacency Labels for Subgraphs of Cartesian Products Esperet, Louis Harms, Nathaniel Zamaraev, Viktor Adjacency labeling schemes Cartesian product Hypercubes For any hereditary graph class ℱ, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in ℱ. As a consequence, we show that, if ℱ 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 ℱ do too. Our proof uses ideas from randomized communication complexity and hashing, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louis Esperet and Nathaniel Harms and Viktor Zamaraev 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.57 urn:nbn:de:0030-drops-181093 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.57 eng https://creativecommons.org/licenses/by/4.0/legalcode