Trees with a given number of leaves and the maximal number of maximum independent sets

zbMath1475.05143MaRDI QIDQ2031165

Dmitriy S. Taletskii, Dmitriy S. Malyshev

Publication date: 8 June 2021

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

zbMATH Keywords

independent set; maximum independent set; maximal independent set; extremal tree

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Merrifield - Simmons indices and Hosoya indices of trees with \(k\) pendant vertices
• Graphs with unique maximum independent sets
• The number of maximal independent sets in a connected graph
• Maximal independent sets in graphs with at most one cycle
• Trees without twin-leaves with smallest number of maximal independent sets
• Graphs, partitions and Fibonacci numbers
• Maximal independent sets in bipartite graphs
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• The structure and maximum number of maximum independent sets in trees
• On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Maximizing the number of independent subsets over trees with bounded degree
• On cliques in graphs
• The number of maximum independent sets in graphs