Maximal independent sets in caterpillar graphs

DOI10.1016/j.dam.2011.10.024zbMath1236.05154MaRDI QIDQ765369

Mónica Villanueva, Carmen Z. Ortiz

Publication date: 19 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.024

zbMATH Keywords

intersection graph; graph algorithms; clique graph; caterpillar graph; enumeration of maximal independent sets; independent graph

Mathematics Subject Classification ID

05C30: Enumeration in graph theory

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

Related Items

Cluster-Based Energy-Efficient Secure Routing in Wireless Sensor Networks, Colouring a dominating set without conflicts: \(q\)-subset square colouring, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Maximal independent sets in a generalisation of caterpillar graph, Coloring a dominating set without conflicts: \(q\)-subset square coloring, Maximal independent sets in grid graphs, Unnamed Item, Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A new backtracking algorithm for generating the family of maximal independent sets of a graph
• The maximum number of maximal independent sets in unicyclic connected graphs
• Counting the number of independent sets in chordal graphs
• Trees with extremal numbers of maximal independent sets including the set of leaves
• Tree-thickness and caterpillar-thickness under girth constraints
• The number of maximal independent sets in a connected graph
• On generating all maximal independent sets
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• The number of maximal independent sets in connected triangle-free graphs
• Maximal independent sets in graphs with at most one cycle
• A finiteness theorem for maximal independent sets
• The number of independent sets in unicyclic graphs
• Maximal independent sets in bipartite graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Maximal independent sets in graphs with at mostr cycles
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• The number of maximal independent sets in connected graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Generate all maximal independent sets in permutation graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Algorithms and Computation
• The Transitive Reduction of a Directed Graph
• On cliques in graphs