The number of maximal independent sets in connected triangle-free graphs

DOI10.1016/S0012-365X(99)90057-2MaRDI QIDQ1292823zbMATH OpenOpenAlexFDO

Authors Min-Jen Jou, Gerard Jennhwa Chang

Publication date 9 August 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)90057-2

zbMATH Keywords

extremal graphstriangle-free graphmaximal independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Recommendations

• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of maximal independent sets in a connected graph
• Size and independence in triangle‐free graphs with maximum degree three
• The number of maximal independent sets in connected graphs

Cites work

• scientific article; zbMATH DE number 19181 (Why is no real title available?)
• scientific article; zbMATH DE number 1465674 (Why is no real title available?)
• scientific article; zbMATH DE number 808335 (Why is no real title available?)
• scientific article; zbMATH DE number 2188478 (Why is no real title available?)
• A Note on Independent Sets in Trees
• A finiteness theorem for maximal independent sets
• An upper bound on the number of cliques in a graph
• Bipartite graphs can have any number of independent sets
• Graphs with unique maximum independent sets
• Maximal independent sets in bipartite graphs
• Maximal independent sets in graphs with at most one cycle
• On cliques in graphs
• On generating all maximal independent sets
• On maximal independent sets of nodes in trees
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The Number of Maximal Independent Sets in a Tree
• The cardinality of the collection of maximum independent sets of a functional graph
• The maximum number of cliques in dense graphs
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected graphs
• The structure and maximum number of maximum independent sets in trees

Cited in

(23)

• Maximal triangle‐free graphs with restrictions on the degrees
• Constraints on the number of maximal independent sets in graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of maximal independent sets in a connected graph
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Independent sets in graphs
• scientific article; zbMATH DE number 3941587 (Why is no real title available?)
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• A note on the independence number of triangle-free graphs. II
• Maximizing the number of independent sets of fixed size in connected graphs with given independence number
• Maximal independent sets in caterpillar graphs
• Graphs with the second largest number of maximal independent sets
• Coverings, matchings and the number of maximal independent sets of graphs
• The minimum number of maximal independent sets in twin-free graphs
• On graphs with the third largest number of maximal independent sets
• Maximal independent sets and regularity of graphs
• The maximum number of maximal independent sets in unicyclic connected graphs
• On the number of independent sets in cycle-separated tricyclic graphs
• Maximal independent sets in bipartite graphs
• scientific article; zbMATH DE number 1151823 (Why is no real title available?)
• On the third largest number of maximal independent sets of graphs
• The number of maximal independent sets in connected graphs
• Maximal independent sets in grid graphs

This page was built for publication: The number of maximal independent sets in connected triangle-free graphs

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