Inducibility of topological trees

DOI10.2989/16073606.2018.1497725MaRDI QIDQ5228893zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2019

Published in Quaestiones Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.06696

zbMATH Keywords

starsinducibilitycaterpillarsmaximum density\(d\)-ary treesleaf-induced subtreestopological treesdegree-restricted treeslimiting minimum density

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Trees without vertices of degree $2$ are sometimes named topological trees. In this work, we bring forward the study of the inducibility of (rooted) topological trees with a given number of leaves. The inducibility of a topological tree $S$ is the limit superior of the proportion of all subsets of leaves of $T$ that induce a copy of $S$ as the size of $T$ grows to infinity. In particular, this relaxes the degree-restriction for the existing notion of the inducibility in $d$-ary trees. We discuss some of the properties of this generalised concept and investigate its connection with the degree-restricted inducibility. In addition, we prove that stars and binary caterpillars are the only topological trees that have an inducibility of $1$. We also find an explicit lower bound on the limit inferior of the proportion of all subsets of leaves of $T$ that induce either a star or a binary caterpillar as the size of $T$ tends to infinity.

Recommendations

• Inducibility of \(d\)-ary trees
• On the inducibility of small trees
• Further results on the inducibility of \(d\)-ary trees
• Inducibility and universality for trees
• Inducibility in binary trees and crossings in random tanglegrams

Cites work

• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• Further results on the inducibility of \(d\)-ary trees
• Inducibility in binary trees and crossings in random tanglegrams
• Inducibility of \(d\)-ary trees
• Mathematical Models in Biology
• On the local profiles of trees
• The inducibility of graphs
• The on-line encyclopedia of integer sequences

Cited in

(9)

• The minimum asymptotic density of binary caterpillars
• Topological ubiquity of trees
• Further results on the inducibility of \(d\)-ary trees
• Induced and weak induced arboricities
• Leaf-induced subtrees of leaf-Fibonacci trees
• Inducibility in binary trees and crossings in random tanglegrams
• Inducibility of \(d\)-ary trees
• On the inducibility of small trees
• Inducibility and universality for trees

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Inducibility of topological trees

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