Trees with minimum number of infima closed sets

DOI10.1016/J.DISC.2021.112793MaRDI QIDQ2113344zbMATH OpenOpenAlexFDO

Authors Eric Ould Dadah Andriantiana, Stephan Wagner

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic estimaterooted treesminimum numberinfima closed sets

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Abstract: Let $T$ be a rooted tree, and $V(T)$ its set of vertices. A subset $X$ of $V(T)$ is called an infima closed set of $T$ if for any two vertices $u,vinX$, the first common ancestor of $u$ and $v$ is also in $X$. This paper determines the trees with minimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with $n$ vertices is also provided.

Recommendations

• On the lower length of the closed-set lattice of a tree
• On trees and tree dimension of ordered sets
• scientific article; zbMATH DE number 475613
• Transversals in trees
• Vertices contained in every minimum dominating set of a tree

Cites work

• scientific article; zbMATH DE number 3435566 (Why is no real title available?)
• Addendum to: Twelve countings with rooted plane trees
• Asymptotics of the extremal values of certain graph parameters in trees with bounded degree
• Graphs with few total dominating sets
• Irrationality of growth constants associated with polynomial recursions
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• On subtrees of trees
• Problems related to graph indices in trees
• Recurrence among trees with most numerous efficient dominating sets
• The Number of Maximal Independent Sets in a Tree
• The maximum number of minimal dominating sets in a tree
• The number of maximum matchings in a tree
• The structure and maximum number of maximum independent sets in trees
• Transcendency of some constants related to integer sequences of polynomial iterations
• Trees having many minimal dominating sets
• Trees with extremal numbers of dominating sets
• Trees with maximum number of maximal matchings
• Twelve countings with rooted plane trees

This page was built for publication: Trees with minimum number of infima closed sets

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