On the inducibility of small trees

MaRDI QIDQ5207849zbMATH OpenFDO

Authors Audace A. V. Dossou-Olory, Stephan Wagner

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1811.12010, https://dmtcs.episciences.org/5804/pdf

binary tree \(d\)-ary tree inducibility maximum density topological tree ternary tree leaf-induced subtree

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex degrees (05C07) Enumeration in graph theory (05C30)

Abstract: 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

1

)

S

with

k

leaves in an arbitrary tree with sufficiently large number of leaves is called the inducibility of

S

. Its precise value is known only for some specific families of trees, most of them exhibiting a symmetrical configuration. In an attempt to answer a recent question posed by Czabarka, Sz'ekely, and the second author of this article, we provide bounds for the inducibility

J (A_{5})

of the

5

-leaf binary tree

A_{5}

whose branches are a single leaf and the complete binary tree of height

2

. It was indicated before that

J (A_{5})

appears to be `close' to

1 / 4

. We can make this precise by showing that

0.24707 l d o t s l e q J (A_{5}) l e q 0.24745 l d o t s

. Furthermore, we also consider the problem of determining the inducibility of the tree

Q_{4}

, which is the only tree among

4

-leaf topological trees for which the inducibility is unknown.

Recommendations

Cited in

(5)

This page was built for publication: On the inducibility of small trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207849)