Generalised outerplanar Turán numbers and maximum number of k-vertex subtrees

DOI10.1016/J.DAM.2021.10.017MaRDI QIDQ2057597zbMATHOpenAlexFDO

Authors Dávid Matolcsi, Zoltán Lóránt Nagy

Publication date 7 December 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphsouterplanar graphsCatalan sequencenumber of subtrees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Abstract: We prove an asymptotic result on the maximum number of k-vertex subtrees in binary trees of given order. This problem turns out to be equivalent to determine the maximum number of k+2-cycles in n-vertex outerplanar graphs, thus we settle the generalized outerplanar Tur'an number for all cycles. We also determine the exponential growth of the generalized outerplanar Tur'an number of paths Pk as a function of k which implies the order of magnitude of the generalized outerplanar Tur'an number of arbitrary trees. The bounds are strongly related to the sequence of Catalan numbers.

Recommendations

• Generalized outerplanar Turán number of short paths
• Outerplanar Turán numbers of cycles and paths
• On the maximum number of cycles in outerplanar and series-parallel graphs
• On the maximum number of cycles in outerplanar and series-parallel graphs
• Generalized planar Turán numbers

Cites work

• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Binary trees with the largest number of subtrees
• Connectivity, graph minors, and subgraph multiplicity
• Coupon-coloring and total domination in Hamiltonian planar triangulations
• Enumeration of subtrees of trees
• Extremal values of ratios: distance problems vs. subtree problems in trees. II
• Greedy trees, subtrees and antichains
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Many \(T\) copies in \(H\)-free graphs
• On subtrees of trees
• On the frequency of 3-connected subgraphs of planar graphs
• On the number of cycles of lengthk in a maximal planar graph

Cited in

(2)

• Generalized outerplanar Turán number of short paths
• Outerplanar Turán numbers of cycles and paths

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Generalised outerplanar Turán numbers and maximum number of \(k\)-vertex subtrees

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