40 citations · 172 across the 51 of their papers we have counts for
67 papers
The distribution of the maximum protection number in simply generated trees
Clemens Heuberger, Sarah J. Selkirk, Stephan Wagner
The protection number of a vertex in a tree is the length of the shortest path from to any leaf contained in the maximal subtree where is the root. In this paper, we de…
Conditioned Galton-Watson trees: The shape functional, and more on the sum of powers of subtree sizes and its mean
James Allen Fill, Svante Janson, Stephan Wagner
For a complex number , we consider the sum of the th powers of subtree sizes in Galton--Watson trees conditioned to be of size . Limiting distributions of this functional…
The Uncover Process for Random Labeled Trees
Benjamin Hackl, Alois Panholzer, Stephan Wagner
We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with vertices is generated uniformly at random. The…
The distribution of the number of automorphisms of random trees
Christoffer Olsson, Stephan Wagner
We study the size of the automorphism group of two different types of random trees: Galton--Watson trees and rooted Pólya trees. In both cases, we prove that it asymptotically foll…
The minimum number of maximal independent sets in twin-free graphs
Stijn Cambie, Stephan Wagner
The problem of determining the maximum number of maximal independent sets in certain graph classes dates back to a paper of Miller and Muller and a question of Erdős and Moser from…
Trees maximizing the number of almost-perfect matchings
Stijn Cambie, Bradley McCoy, Gunjan Sharma +2
We characterize the extremal trees that maximize the number of almost-perfect matchings, which are matchings covering all but one or two vertices, and those that maximize the numbe…
On the distribution of eigenvalues of increasing trees
Kenneth Dadedzi, Stephan Wagner
We prove that the multiplicity of a fixed eigenvalue in a random recursive tree on vertices satisfies a central limit theorem with mean and variance asymptotically equal to…
Refined enumeration of -plane trees and -noncrossing trees
Isaac Owino Okoth, Stephan Wagner
A -plane tree is a plane tree whose vertices are assigned labels between and in such a way that the sum of the labels along any edge is no greater than . These tree…
Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo
Clemens Heuberger, Sarah J. Selkirk, Stephan Wagner
For fixed non-negative integers , , and , with , a -Dyck path of length is a lattice path that starts at , ends at , stays weakly…
Convex characters, algorithms and matchings
Steven Kelk, Ruben Meuwese, Stephan Wagner
Phylogenetic trees are used to model evolution: leaves are labelled to represent contemporary species ("taxa") and interior vertices represent extinct ancestors. Informally, convex…
Broadcasting induced colourings of random recursive trees and preferential attachment trees
Colin Desmarais, Cecilia Holmgren, Stephan Wagner
In this work we consider random two-colourings of random linear preferential attachment trees, which includes random recursive trees, random plane-oriented recursive trees, random…
Distinct Fringe Subtrees in Random Trees
Louisa Seelbach Benkner, Stephan Wagner
A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees…
On the maximum mean subtree order of trees
Stijn Cambie, Stephan Wagner, Hua Wang
A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invaria…
The birth of the strong components
Sergey Dovgal, Élie de Panafieu, Dimbinaina Ralaivaosaona +2
Random directed graphs undergo a phase transition around the point , and the width of the transition window has been known since the works of Luczak and Seierstad…
Extremal trees with fixed degree sequence
Eric O. D. Andriantiana, Valisoa Razanajatovo Misanantenaina, Stephan Wagner
The greedy tree and the -tree are known to be extremal among trees with degree sequence with respect to various graph invariants.…
Trees with minimum number of infima closed sets
Eric Ould Dadah Andriantiana, Stephan Wagner
Let be a rooted tree, and its set of vertices. A subset of is called an infima closed set of if for any two vertices , the first common ancestor…
Irrationality of growth constants associated with polynomial recursions
Stephan Wagner, Volker Ziegler
We consider integer sequences that satisfy a recursion of the form for some polynomial of degree . If such a sequence tends to infinity, then it satis…
On the Collection of Fringe Subtrees in Random Binary Trees
Louisa Seelbach Benkner, Stephan Wagner
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic…
On the probability that a random subtree is spanning
Stephan Wagner
We consider the quantity associated with a graph that is defined as the probability that a randomly chosen subtree of is spanning. Motivated by conjectures due to Ch…
The average size of matchings in graphs
Eric O. D. Andriantiana, Valisoa Razanajatovo Misanantenaina, Stephan Wagner
In this paper, we consider the average size of independent edge sets, also called matchings, in a graph. We characterize the extremal graphs for the average size of matchings in ge…
On two subclasses of Motzkin paths and their relation to ternary trees
Helmut Prodinger, Sarah J. Selkirk, Stephan Wagner
Two subclasses of Motzkin paths, S-Motzkin and T-Motzkin paths, are introduced. We provide bijections between S-Motzkin paths and ternary trees, S-Motzkin paths and non-crossing tr…
On the inducibility of small trees
Audace A. V. Dossou-Olory, Stephan Wagner
The quantity that captures the asymptotic value of the maximum number of appearances of a given topological tree (a rooted tree with no vertices of outdegree ) with leav…
Further results on the inducibility of -ary trees
Audace A. V. Dossou-Olory, Stephan Wagner
A subset of leaves of a rooted tree induces a new tree in a natural way. The density of a tree inside a larger tree is the proportion of such leaf-induced subtrees in t…
A central limit theorem for almost local additive tree functionals
Dimbinaina Ralaivaosaona, Matas Šileikis, Stephan Wagner
An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll functio…