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

DOI10.1016/J.DAM.2021.10.017zbMATH Open1479.05158arXiv2102.11746OpenAlexW3213290792MaRDI QIDQ2057597FDOQ2057597

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)

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)