Near-optimal induced universal graphs for cycles and paths (Q2185721)

A graph is said to be an induced universal graph for a family \(F\) of graphs if it contains each graph in \(F\) as a vertex-induced subgraph. Recently, it was shown by many authors the existence of an induced universal graph with various numbers of vertices for the family of all undirected graphs on \(n\) vertices; each claims to improve the previous best bound. The present paper continues 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, it can be shown that the smallest induced universal graph has certain size, but it remains to find the constant hidden in the \(o\)-notation. In order to find the correct constants for general degree \(D>0\), it is natural first to consider the case \(D=2\). For \(D=2\), several results are known. The present paper constructs for \(D=2\) an even smaller induced universal graph with \(2n-1\) vertices, thereby confirming the existence of such a graph with \(2n+o(n)\) vertices. For the family of acyclic graphs on \(n\) vertices with maximum degree 2, the paper gives a size for the smallest induced universal graph, and also introduces the notion of size oblivious and size aware decoding, and relates this to families of induced universal graphs. Finally, the paper gives new upper and lower bounds on the complexity of size aware and size oblivious decoders for the family of graphs consisting of a single cycle.