4 papers · 1 filter
Functionality of Random Graphs
John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
The functionality of a graph is the minimum number such that in every induced subgraph of there exists a vertex whose neighbourhood is uniquely determined by the neighb…
Boolean combinations of graphs
Sarosh Adenwalla, Samuel Braunfeld, John Sylvester +1
Boolean combinations allow combining given combinatorial objects to obtain new, potentially more complicated, objects. In this paper, we initiate a systematic study of this idea ap…
Adjacency Labeling Schemes for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +1
A graph class admits an implicit representation if, for every positive integer , its -vertex graphs have a -bit (adjacency) labeling scheme, i.e., their vertices c…
Symmetric-Difference (Degeneracy) and Signed Tree Models
Édouard Bonnet, Julien Duron, John Sylvester +1
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…