Inducibility of topological trees

DOI10.2989/16073606.2018.1497725zbMATH Open1417.05027arXiv1802.06696OpenAlexW2962963863MaRDI QIDQ5228893FDOQ5228893

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

Publication date: 13 August 2019

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• The on-line encyclopedia of integer sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mathematical Models in Biology
• The inducibility of graphs
• On the local profiles of trees
• Inducibility of \(d\)-ary trees
• Inducibility in binary trees and crossings in random tanglegrams
• Further results on the inducibility of \(d\)-ary trees

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

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)