7 papers
Set-defined graph classes: -boundedness meets tropical algebra
Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons +2
We study set-defined graph classes: hereditary classes whose vertices are assigned fixed-length numerical tuples, with adjacency determined solely by equality patterns among coordi…
Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Andreas Göbel, Nicolas Klodt +3
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs on the same vertex set, and asks for a walk of s…
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…
Tight bounds on adjacency labels for monotone graph classes
Édouard Bonnet, Julien Duron, John Sylvester +2
A class of graphs admits an adjacency labeling scheme of size , if the vertices in each of its -vertex graphs can be assigned binary strings (called labels) of length $b(n…