论文标题
笛卡尔产品子图的最佳邻接标签
Optimal Adjacency Labels for Subgraphs of Cartesian Products
论文作者
论文摘要
对于任何遗传图级$ f $，我们为$ f $中的笛卡尔产品的子图和诱导子图的类别构建了最佳邻接标签方案。结果，我们表明，如果$ f $接收有效的邻接标签（或等效地符合诱导的普通图），那么符合信息理论的最低限度，则在$ f $中的YNEL类和诱导的图形产品的诱导次级分类也可以。我们的证明使用了随机通信复杂性，哈希和加性组合学的想法，并根据Chepoi，Labourel和Ratel的最新结果改进[Graph Doemhs Journal，2020年]。
For any hereditary graph class $F$, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$. As a consequence, we show that, if $F$ 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 $F$ do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].
