Trees with minimum number of infima closed sets

DOI10.1016/J.DISC.2021.112793zbMATH Open1484.05038arXiv2008.10225OpenAlexW4205603664MaRDI QIDQ2113344FDOQ2113344

Eric Ould Dadah Andriantiana, Stephan Wagner

Publication date: 14 March 2022

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

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.

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

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

zbMATH Keywords

asymptotic estimaterooted treesminimum numberinfima closed sets

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On subtrees of trees
• Title not available (Why is that?)
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Trees having many minimal dominating sets
• The structure and maximum number of maximum independent sets in trees
• Twelve countings with rooted plane trees
• The Number of Maximal Independent Sets in a Tree
• The number of maximum matchings in a tree
• Title not available (Why is that?)
• Trees with maximum number of maximal matchings
• Graphs with few total dominating sets
• Addendum to: Twelve countings with rooted plane trees
• Title not available (Why is that?)
• Problems related to graph indices in trees
• Transcendency of some constants related to integer sequences of polynomial iterations
• The Maximum Number of Minimal Dominating Sets in a Tree
• Irrationality of growth constants associated with polynomial recursions

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)