BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Stephan Wagner

Stephan Wagner appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRmath.NTDiscrete Mathematicscond-mat.stat-mechData Structures and AlgorithmsLogic in Computer Sciencemath-phmath.CAmath.GRmath.MPmath.OA

Catalog footprint

What is connected

35works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

35 published item(s)

preprint2023arXiv

The Uncover Process for Random Labeled Trees

We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with $n$ vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this work: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A polynomial associated with rooted trees and specific posets

We investigate a trivariate polynomial associated with rooted trees. It generalises a bivariate polynomial for rooted trees that was recently introduced by Liu. We show that this polynomial satisfies a deletion-contraction recursion and can be expressed as a sum over maximal antichains. Several combinatorial quantities can be obtained as special values, in particular the number of antichains, maximal antichains and cutsets. We prove that two of the three possible bivariate specialisations characterise trees uniquely up to isomorphism. One of these has already been established by Liu, the other is new. For the third specialisation, we construct non-isomorphic trees with the same associated polynomial. We finally find that our polynomial can be generalised in a natural way to a family of posets that we call $\mathcal{V}$-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing $\mathcal{V}$-posets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the distribution of eigenvalues of increasing trees

We prove that the multiplicity of a fixed eigenvalue $α$ in a random recursive tree on $n$ vertices satisfies a central limit theorem with mean and variance asymptotically equal to $μ_α n$ and $σ^2_α n$ respectively. It is also shown that $μ_α$ and $σ^2_α$ are positive for every totally real algebraic integer. The proofs are based on a general result on additive tree functionals due to Holmgren and Janson. In the case of the eigenvalue $0$, the constants $μ_0$ and $σ^2_0$ can be determined explicitly by means of generating functions. Analogous results are also obtained for Laplacian eigenvalues and binary increasing trees.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Refined enumeration of $k$-plane trees and $k$-noncrossing trees

A $k$-plane tree is a plane tree whose vertices are assigned labels between $1$ and $k$ in such a way that the sum of the labels along any edge is no greater than $k+1$. These trees are known to be related to $(k+1)$-ary trees, and they are counted by a generalised version of the Catalan numbers. We prove a surprisingly simple refined counting formula, where we count trees with a prescribed number of labels of each kind. Several corollaries are derived from this formula, and an analogous theorem is proven for $k$-noncrossing trees, a similarly defined family of labelled noncrossing trees that are related to $(2k+1)$-ary trees.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The birth of the strong components

Random directed graphs $D(n,p)$ undergo a phase transition around the point $p = 1/n$, and the width of the transition window has been known since the works of Luczak and Seierstad. They have established that as $n \to \infty$ when $p = (1 + μn^{-1/3})/n$, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as $μ$ goes from $-\infty$ to $\infty$. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of $μ$ and provide more properties of the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter $p$, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Extremal trees with fixed degree sequence

The greedy tree $\mathcal{G}(D)$ and the $\mathcal{M}$-tree $\mathcal{M}(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which $\mathcal{G}(D)$ or $\mathcal{M}(D)$ is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence $D$ to the set of trees whose degree sequence is majorised by a given sequence $D$, which also has a number of applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Further results on the inducibility of $d$-ary trees

A subset of leaves of a rooted tree induces a new tree in a natural way. The density of a tree $D$ inside a larger tree $T$ is the proportion of such leaf-induced subtrees in $T$ that are isomorphic to $D$ among all those with the same number of leaves as $D$. The inducibility of $D$ measures how large this density can be as the size of $T$ tends to infinity. In this paper, we explicitly determine the inducibility in some previously unknown cases and find general upper and lower bounds, in particular in the case where $D$ is balanced, i.e., when its branches have at least almost the same size. Moreover, we prove a result on the speed of convergence of the maximum density of $D$ in strictly $d$-ary trees $T$ (trees where every internal vertex has precisely $d$ children) of a given size $n$ to the inducibility as $n \to \infty$, which supports an open conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Irrationality of growth constants associated with polynomial recursions

We consider integer sequences that satisfy a recursion of the form $x_{n+1} = P(x_n)$ for some polynomial $P$ of degree $d > 1$. If such a sequence tends to infinity, then it satisfies an asymptotic formula of the form $x_n \sim A α^{d^n}$, but little can be said about the constant $α$. In this paper, we show that $α$ is always irrational or an integer. In fact, we prove a stronger statement: if a sequence $G_n$ satisfies an asymptotic formula of the form $G_n = A α^n + B + O(α^{-εn})$, where $A,B$ are algebraic and $α> 1$, and the sequence contains infinitely many integers, then $α$ is irrational or an integer.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Collection of Fringe Subtrees in Random Binary Trees

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 trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees. In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between $c_1n/\sqrt{\ln n}(1+o(1))$ and $c_2n/\sqrt{\ln n}(1+o(1))$ for two constants $c_1 \approx 1.0591261434$ and $c_2 \approx 1.0761505454$, both in expectation and with high probability, where $n$ denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is $n/\ln n$ in this case. Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

$q$-Quasiadditive Functions

In this paper, we introduce the notion of $q$-quasiadditivity of arithmetic functions, as well as the related concept of $q$-quasimultiplicativity, which generalises strong $q$-additivity and -multiplicativity, respectively. We show that there are many natural examples for these concepts, which are characterised by functional equations of the form $f(q^{k+r}a + b) = f(a) + f(b)$ or $f(q^{k+r}a + b) = f(a) f(b)$ for all $b < q^k$ and a fixed parameter $r$. In addition to some elementary properties of $q$-quasiadditive and $q$-quasimultiplicative functions, we prove characterisations of $q$-quasiadditivity and $q$-quasimultiplicativity for the special class of $q$-regular functions. The final main result provides a general central limit theorem that includes both classical and new examples as corollaries.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Additive functionals of $d$-ary increasing trees

A tree functional is called additive if it satisfies a recursion of the form $F(T) = \sum_{j=1}^k F(B_j) + f(T)$, where $B_1,\ldots,B_k$ are the branches of the tree $T$ and $f(T)$ is a toll function. We prove a general central limit theorem for additive functionals of $d$-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalised plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of $d$-ary increasing trees, but many other examples (old and new) are covered as well.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Inducibility in binary trees and crossings in random tanglegrams

In analogy to other concepts of a similar nature, we define the inducibility of a rooted binary tree. Given a fixed rooted binary tree $B$ with $k$ leaves, we let $γ(B,T)$ be the proportion of all subsets of $k$ leaves in $T$ that induce a tree isomorphic to $B$. The inducibility of $B$ is $\limsup_{|T| \to \infty} γ(B,T)$. We determine the inducibility in some special cases, show that every binary tree has positive inducibility and prove that caterpillars are the only binary trees with inducibility $1$. We also formulate some open problems and conjectures on the inducibility. Finally, we present an application to crossing numbers of random tanglegrams.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Limits of subcritical random graphs and random graphs with excluded minors

We prove local convergence results for the uniformly random, labelled or unlabelled, graphs from subcritical families. As an example special case, we prove Benjamini-Schramm convergence for the uniform random unlabelled tree. We introduce a compactification of the space of countable (connected) rooted graphs, and use it to generalise the notion of Benjamini-Schramm convergence in order to allow for vertices of infinite degree in the limit object.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On $q$-Quasiadditive and $q$-Quasimultiplicative Functions

In this paper, we introduce the notion of $q$-quasiadditivity of arithmetic functions, as well as the related concept of $q$-quasimultiplicativity, which generalise strong $q$-additivity and -multiplicativity, respectively. We show that there are many natural examples for these concepts, which are characterised by functional equations of the form $f(q^{k+r}a + b) = f(a) + f(b)$ or $f(q^{k+r}a + b) = f(a) f(b)$ for all $b < q^k$ and a fixed parameter $r$. In addition to some elementary properties of $q$-quasiadditive and $q$-quasimultiplicative functions, we prove characterisations of $q$-quasiadditivity and $q$-quasimultiplicativity for the special class of $q$-regular functions. The final main result provides a general central limit theorem that includes both classical and new examples as corollaries.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the algebraic area of lattice walks and the Hofstadter model

We consider the generating function of the algebraic area of lattice walks, evaluated at a root of unity, and its relation to the Hofstadter model. In particular, we obtain an expression for the generating function of the n-th moments of the Hofstadter Hamiltonian in terms of a complete elliptic integral, evaluated at a rational function. This in turn gives us both exact and asymptotic formulas for these moments.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Paths vs. stars in the local profile of trees

The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees. For a tree $T$, let $p^{(k)}_1(T)$ be the proportion of paths among all $k$-vertex subtrees (induced connected subgraphs) of $T$, and let $p^{(k)}_2(T)$ be the proportion of stars. Our main theorem states: if $p^{(k)}_1(T_n) \to 0$ for a sequence of trees $T_1,T_2,\ldots$ whose size tends to infinity, then $p^{(k)}_2(T_n) \to 1$. Both are also shown to be equivalent to the statement that the number of $k$-vertex subtrees grows superlinearly and the statement that the $(k-1)$th degree moment grows superlinearly.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The shape of random tanglegrams

A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Analysis of Bidirectional Ballot Sequences and Random Walks Ending in their Maximum

Consider non-negative lattice paths ending at their maximum height, which will be called admissible paths. We show that the probability for a lattice path to be admissible is related to the Chebyshev polynomials of the first or second kind, depending on whether the lattice path is defined with a reflective barrier or not. Parameters like the number of admissible paths with given length or the expected height are analyzed asymptotically. Additionally, we use a bijection between admissible random walks and special binary sequences to prove a recent conjecture by Zhao on ballot sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Canonical Trees, Compact Prefix-free Codes and Sums of Unit Fractions: A Probabilistic Analysis

For fixed $t\ge 2$, we consider the class of representations of $1$ as sum of unit fractions whose denominators are powers of $t$ or equivalently the class of canonical compact $t$-ary Huffman codes or equivalently rooted $t$-ary plane "canonical" trees. We study the probabilistic behaviour of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property) and the number of leaves at maximum distance from the root (discrete distribution).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Erdős-Surányi sequences and trigonometric integrals

We study representations of integers as sums of the form $\pm a_1\pm a_2\pm \dotsb \pm a_n$, where $a_1,a_2,\ldots$ is a prescribed sequence of integers. Such a sequence is called an Erdős-Surányi sequence if every integer can be written in this form for some $n\in\mathbb{N}$ and choices of signs in infinitely many ways. We study the number of representations of a fixed integer, which can be written as a trigonometric integral, and obtain an asymptotic formula under a rather general scheme due to Roth and Szekeres. Our approach, which is based on Laplace's method for approximating integrals, can also be easily extended to find higher-order expansions. As a corollary, we settle a conjecture of Andrica and Ionaşcu on the number of solutions to the signum equation $\pm 1^k \pm 2^k \pm \dotsb \pm n^k = 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Hitting Times, Cover Cost, and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are "easier to reach" by a random walk, but "more difficult to get out of". We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self-contained, and puts some known results relating the behaviour or random walk on a graph to its eigenvalues in a new perspective.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multi-Base Representations of Integers: Asymptotic Enumeration and Central Limit Theorems

In a multi-base representation of an integer (in contrast to, for example, the binary or decimal representation) the base (or radix) is replaced by products of powers of single bases. The resulting numeral system has desirable properties for fast arithmetic. It is usually redundant, which means that each integer can have multiple different digit expansions, so the natural question for the number of representations arises. In this paper, we provide a general asymptotic formula for the number of such multi-base representations of a positive integer $n$. Moreover, we prove central limit theorems for the sum of digits, the Hamming weight (number of non-zero digits, which is a measure of efficiency) and the occurrences of a fixed digits in a random representation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The height of multiple edge plane trees

Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that $d$-ary multi-edge trees where the out-degrees are bounded by $d$ are in bijection with classical $d$-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Uniform spanning trees on Sierpinski graphs

We study spanning trees on Sierpinski graphs (i.e., finite approximations to the Sierpinski gasket) that are chosen uniformly at random. We construct a joint probability space for uniform spanning trees on every finite Sierpinski graph and show that this construction gives rise to a multi-type Galton-Watson tree. We derive a number of structural results, for instance on the degree distribution. The connection between uniform spanning trees and loop-erased random walk is then exploited to prove convergence of the latter to a continuous stochastic process. Some geometric properties of this limit process, such as the Hausdorff dimension, are investigated as well. The method is also applicable to other self-similar graphs with a sufficient degree of symmetry.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Compositions into Powers of $b$: Asymptotic Enumeration and Parameters

For a fixed integer base $b\geq2$, we consider the number of compositions of $1$ into a given number of powers of $b$ and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of $b$. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices. With the same techniques the distribution of the largest denominator and the number of distinct parts are investigated.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Enumeration of the adjunctive hierarchy of hereditarily finite sets

Hereditarily finite sets (sets which are finite and have only hereditarily finite sets as members) are basic mathematical and computational objects, and also stand at the basis of some programming languages. This raises the need for efficient representation of such sets, for example by numbers. In 2008, Kirby proposed an adjunctive hierarchy of hereditarily finite sets, based on the fact that they can also be seen as built up from the empty set by repeated adjunction, that is, by the addition of a new single element drawn from the already existing sets to an already existing set. Determining the cardinality $a_n$ of each level of this hierarchy, problem crucial in establishing whether the natural adjunctive hierarchy leads to an efficient encoding by numbers, was left open. In this paper we solve this problem. Our results can be generalized to hereditarily finite sets with atoms, or can be further refined by imposing restrictions on rank, on cardinality, or on the maximum level from where the new adjoined element can be drawn. We also show that $a_n$ satisfies the asymptotic formula $a_n = C^{2^n} + O(C^{2^{n-1}})$, for a constant $C \approx 1.3399$, which is a too fast asymptotic growth for practical purposes. We thus propose a very natural variant of the adjunctive hierarchy, whose asymptotic behavior we prove to be $Θ(2^n)$. To our knowledge, this is the first result of this kind.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Variances and Covariances in the Central Limit Theorem for the Output of a Transducer

We study the joint distribution of the input sum and the output sum of a deterministic transducer. Here, the input of this finite-state machine is a uniformly distributed random sequence. We give a simple combinatorial characterization of transducers for which the output sum has bounded variance, and we also provide algebraic and combinatorial characterizations of transducers for which the covariance of input and output sum is bounded, so that the two are asymptotically independent. Our results are illustrated by several examples, such as transducers that count specific blocks in the binary expansion, the transducer that computes the Gray code, or the transducer that computes the Hamming weight of the width-$w$ non-adjacent form digit expansion. The latter two turn out to be examples of asymptotic independence.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Spectral moments of trees with given degree sequence

Let $λ_1,\dots,λ_n$ be the eigenvalues of a graph $G$. For any $k\geq 0$, the $k$-th spectral moment of $G$ is defined by $\M_k(G)=λ_1^k+\dots+λ_n^k$. We use the fact that $\M_k(G)$ is also the number of closed walks of length $k$ in $G$ to show that among trees $T$ whose degree sequence is $D$ or majorized by $D$, $\M_k(T)$ is maximized by the greedy tree with degree sequence $D$ (constructed by assigning the highest degree in $D$ to the root, the second-, third-, \dots highest degrees to the neighbors of the root, and so on) for any $k\geq 0$. Several corollaries follow, in particular a conjecture of Ilić and Stevanović on trees with given maximum degree, which in turn implies a conjecture of Gutman, Furtula, Marković and Glišić on the Estrada index of such trees, which is defined as $\EE(G)=e^{λ_1}+\dots+e^{λ_n}$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The number of fixed points of Wilf's partition involution

Wilf partitions are partitions of an integer $n$ in which all nonzero multiplicities are distinct. On his webpage, the late Herbert Wilf posed the problem to find "any interesting theorems" about the number f(n) of those partitions. Recently, Fill, Janson and Ward (and independently Kane and Rhoades) determined an asymptotic formula for $\log f(n)$. Since the original motivation for studying Wilf partitions was the fact that the operation that interchanges part sizes and multiplicities is an involution on the set of Wilf partitions, they mentioned as an open problem to determine a similar asymptotic formula for the number of fixed points of this involution, which we denote by F(n). In this short note, we show that the method of Fill, Janson and Ward also applies to F(n). Specifically, we obtain the asymptotic formula $\log F(n) \sim \frac12 \log f(n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Labeled trees, maps, and an algebraic identity

We give a short and direct proof of a remarkable identity that arises in the enumeration of labeled trees with respect to their indegree sequence, where all edges are oriented from the vertex with lower label towards the vertex with higher label. This solves a problem posed by Shin and Zeng in a recent article. We also provide a generalization of this identity that translates to a formula for the number of rooted spanning forests with given indegree sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) $m(T)$ of a tree $T$ of given order. While the trees that attain the lower bound are easily characterised, the trees with largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order $n$ is at most $O(1.391664^n)$ (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).

0 citations0 reviewsNo code linkedOpen access