Constructing graphs with limited resources
From MaRDI portal
Abstract: We discuss the amount of physical resources required to construct a given graph, where vertices are added sequentially. We naturally identify information -- distinct into instructions and memory -- and randomness as resources. Not surprisingly, we show that, in this framework, threshold graphs are the simplest possible graphs, since the construction of threshold graphs requires a single bit of instructions for each vertex and no use of memory. Large instructions without memory do not bring any advantage. With one bit of instructions and one bit of memory for each vertex, we can construct a family of perfect graphs that strictly includes threshold graphs. We consider the case in which memory lasts for a single time step, and show that as well as the standard threshold graphs, linear forests are also producible. We show further that the number of random bits (with no memory or instructions) needed to construct any graph is asymptotically the same as required for the ErdH{o}s-R'enyi random graph. We also briefly consider constructing trees in this scheme. The problem of defining a hierarchy of graphs in the proposed framework is fully open.
This page was built for publication: Constructing graphs with limited resources
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6298289)
