TY - JOUR

T1 - Near-optimal induced universal graphs for cycles and paths

AU - Abrahamsen, Mikkel

AU - Alstrup, Stephen

AU - Holm, Jacob

AU - Knudsen, Mathias Bæk Tejs

AU - Stöckel, Morten

PY - 2020

Y1 - 2020

N2 - A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an induced universal graph with (1+o(1))⋅2(n−1)∕2 vertices improving the previous best bound of 16⋅2n∕2 by Alstrup et al. (2015) and matching the lower bound of 2(n−1)∕2 by Moon (1965) up to lower order additive terms. We continue this line of research of finding the size of the smallest induced universal graph up to lower order additive terms for some basic graph families. For the family of graphs with n vertices and bounded degree D=O(1), Alon and Nenadov [Math. Proc. Camb. Philos. Soc. 2017] [4] showed that the smallest induced universal graph has size ΘnD∕2, but it remains to find the constant hidden in the O-notation. For even D the bound OnD∕2 was already shown by Butler (2009). In order to find the correct constants for general D>0, it is natural first to consider the case D=2. For D=2, Butler gave an induced universal graph of size 6.5n and subsequently, Esperet et al. (2008) found an induced universal graph for D=2 of size 2.5n. We construct for D=2 an even smaller induced universal graph with 2n−1 vertices. This proves a conjecture by Esperet et al. stating the existence of such a graph with 2n+o(n) vertices. For the family of acyclic graphs on n vertices with maximum degree 2 we show that the smallest induced universal graph has size [Formula presented]. We also introduce the notion of size oblivious and size aware decoding, and relate this to families of induced universal graphs. For the family of graphs consisting of a single cycle we prove new upper and lower bounds on the complexity of size aware and size oblivious decoders. These new bounds separate the two notions.

AB - A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an induced universal graph with (1+o(1))⋅2(n−1)∕2 vertices improving the previous best bound of 16⋅2n∕2 by Alstrup et al. (2015) and matching the lower bound of 2(n−1)∕2 by Moon (1965) up to lower order additive terms. We continue this line of research of finding the size of the smallest induced universal graph up to lower order additive terms for some basic graph families. For the family of graphs with n vertices and bounded degree D=O(1), Alon and Nenadov [Math. Proc. Camb. Philos. Soc. 2017] [4] showed that the smallest induced universal graph has size ΘnD∕2, but it remains to find the constant hidden in the O-notation. For even D the bound OnD∕2 was already shown by Butler (2009). In order to find the correct constants for general D>0, it is natural first to consider the case D=2. For D=2, Butler gave an induced universal graph of size 6.5n and subsequently, Esperet et al. (2008) found an induced universal graph for D=2 of size 2.5n. We construct for D=2 an even smaller induced universal graph with 2n−1 vertices. This proves a conjecture by Esperet et al. stating the existence of such a graph with 2n+o(n) vertices. For the family of acyclic graphs on n vertices with maximum degree 2 we show that the smallest induced universal graph has size [Formula presented]. We also introduce the notion of size oblivious and size aware decoding, and relate this to families of induced universal graphs. For the family of graphs consisting of a single cycle we prove new upper and lower bounds on the complexity of size aware and size oblivious decoders. These new bounds separate the two notions.

KW - Adjacency labeling schemes

KW - Bounded degree graphs

KW - Distributed computing

KW - Induced universal graphs

UR - http://www.scopus.com/inward/record.url?scp=85075523198&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.10.030

DO - 10.1016/j.dam.2019.10.030

M3 - Journal article

AN - SCOPUS:85075523198

VL - 282

SP - 1

EP - 13

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -