Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTrees with minimum number of infima closed sets
207
0
0.0
(
0
)
Added by
Eric Ould Dadah Andriantiana
Publication date
2020
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic 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,vin X$, 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.
rate research
Read More
A subset of vertices is a {it maximum independent set} if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a {it maximum dissociation set} if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito [J. Graph Theory {bf 15} (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order $n$ is $2^{frac{n-3}{2}}$ if $n$ is odd, and $2^{frac{n-2}{2}}+1$ if $n$ is even and also characterized all extremal trees with the most maximum independent sets, which solved a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of $k$-K{o}nig-Egerv{a}ry graph, we show that the maximum number of maximum dissociation sets in a tree of order $n$ is begin{center} $left{ begin{array}{ll} 3^{frac{n}{3}-1}+frac{n}{3}+1, & hbox{if $nequiv0pmod{3}$;} 3^{frac{n-1}{3}-1}+1, & hbox{if $nequiv1pmod{3}$;} 3^{frac{n-2}{3}-1}, & hbox{if $nequiv2pmod{3}$,} end{array} right.$ end{center} and also give complete structural descriptions of all extremal trees on which these maxima are achieved.
Weighted Szeged index is a recently introduced extension of the well-known Szeged index. In this paper, we present a new tool to analyze and characterize minimum weighted Szeged index trees. We exhibit the best trees with up to 81 vertices and use this information, together with our results, to propose various conjectures on the structure of minimum weighted Szeged index trees.
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
As a fundamental research object, the minimum edge dominating set (MEDS) problem is of both theoretical and practical interest. However, determining the size of a MEDS and the number of all MEDSs in a general graph is NP-hard, and it thus makes sense to find special graphs for which the MEDS problem can be exactly solved. In this paper, we study analytically the MEDS problem in the pseudofractal scale-free web and the Sierpinski gasket with the same number of vertices and edges. For both graphs, we obtain exact expressions for the edge domination number, as well as recursive solutions to the number of distinct MEDSs. In the pseudofractal scale-free web, the edge domination number is one-ninth of the number of edges, which is three-fifths of the edge domination number of the Sierpinski gasket. Moreover, the number of all MEDSs in the pseudofractal scale-free web is also less than that corresponding to the Sierpinski gasket. We argue that the difference of the size and number of MEDSs between the two studied graphs lies in the scale-free topology.
We show that the number of partial triangulations of a set of $n$ points on the plane is at least the $(n-2)$-nd Catalan number. This is tight for convex $n$-gons. We also describe all the equality cases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
