Maximal independent sets in caterpillar graphs

DOI10.1016/j.dam.2011.10.024zbMath1236.05154OpenAlexW2069114326MaRDI 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 graphgraph algorithmsclique graphcaterpillar graphenumeration of maximal independent setsindependent graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Unnamed Item ⋮ Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars ⋮ 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 grid graphs ⋮ Maximal independent sets in a generalisation of caterpillar graph ⋮ Cluster-Based Energy-Efficient Secure Routing in Wireless Sensor Networks ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring

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

This page was built for publication: Maximal independent sets in caterpillar graphs