Trees with given stability number and minimum number of stable sets

DOI10.1007/S00373-011-1041-2MaRDI QIDQ1926055zbMATH OpenOpenAlexFDO

Authors Véronique Bruyère, Gwenaël Joret, Hadrien Mélot

Publication date 27 December 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Fibonacci numberMerrifield-Simmons indexstability number

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We study the structure of trees minimizing their number of stable sets for given order $n$ and stability number $alpha$. Our main result is that the edges of a non-trivial extremal tree can be partitioned into $n-alpha$ stars, each of size $lceilfracn-1n-alphaceil$ or $lfloorfracn-1n-alphafloor$, so that every vertex is included in at most two distinct stars, and the centers of these stars form a stable set of the tree.

Recommendations

• The intersection of all maximum stable sets of a tree and its pendant vertices
• scientific article; zbMATH DE number 1735714
• The minimal number of subtrees with a given degree sequence
• The structure and maximum number of maximum independent sets in trees
• The number of independent sets intersecting the set of leaves in trees.

Cites work

• An entropy approach to the hard-core model on bipartite graphs
• An upper bound on the number of independent sets in a tree.
• Bounds on the number of vertex independent sets in a graph
• Facet defining inequalities among graph invariants: The system graphedron
• Fibonacci index and stability number of graphs: a polyhedral study
• Graphs, partitions and Fibonacci numbers
• scientific article; zbMATH DE number 4074878 (Why is no real title available?)
• scientific article; zbMATH DE number 3745213 (Why is no real title available?)
• scientific article; zbMATH DE number 808335 (Why is no real title available?)
• scientific article; zbMATH DE number 1391668 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Maximizing the number of independent subsets over trees with bounded degree
• On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs
• On the Merrifield-Simmons index of trees
• The first and second largest Merrifield-Simmons indices of trees with prescribed pendent vertices
• The Merrifield - Simmons indices and Hosoya indices of trees with \(k\) pendant vertices
• The Merrifield-Simmons index in (n,n+ 1)-graphs
• The number of independent sets in unicyclic graphs
• The number of independent sets in unicyclic graphs with a given diameter
• Tricyclic graphs with maximum Merrifield-Simmons index
• Unicycle graphs with extremal Merrifield-Simmons index

Cited in

(5)

• Maximizing the number of independent sets of fixed size in connected graphs with given independence number
• Minimum d-transversals of maximum-weight stable sets in trees
• scientific article; zbMATH DE number 1735713 (Why is no real title available?)
• On the maximum number of maximum independent sets of bipartite graphs
• The intersection of all maximum stable sets of a tree and its pendant vertices

Describes a project that uses

Uses Software

• GraPHedron

This page was built for publication: Trees with given stability number and minimum number of stable sets

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