4 papers
Broadcasting on random recursive trees
Louigi Addario-Berry, Luc Devroye, Gabor Lugosi +1
We study the broadcasting problem when the underlying tree is a random recursive tree. The root of the tree has a random bit value assigned. Every other vertex has the same bit val…
Minor-Obstructions for Apex Sub-unicyclic Graphs
Alexandros Leivaditis, Alexandros Singh, Giannos Stamoulis +3
A graph is sub-unicyclic if it contains at most one cycle. We also say that a graph is -apex sub-unicyclic if it can become sub-unicyclic by removing of its vertices. We…
Structure and enumeration of K4-minor-free links and link-diagrams
Juanjo Rué, Dimitrios M. Thilikos, Vasiliki Velona
We study the class L of link-types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4.…
Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
Vasiliki Velona
Let be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function which cou…