Maximal independent sets in caterpillar graphs

DOI10.1016/J.DAM.2011.10.024zbMATH Open1236.05154OpenAlexW2069114326MaRDI QIDQ765369FDOQ765369

Authors: 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

Recommendations

• Maximal independent sets in a generalisation of caterpillar graph
• scientific article; zbMATH DE number 2188328
• On caterpillar factors in graphs
• scientific article
• scientific article

zbMATH Keywords

graph algorithmsintersection graphclique graphcaterpillar graphenumeration of maximal independent setsindependent graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Maximal independent sets in grid graphs
• On the number of maximal independent sets of vertices in star-like ladders
• On the maximum number of maximum independent sets of bipartite graphs
• Cluster-Based Energy-Efficient Secure Routing in Wireless Sensor Networks
• Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Title not available (Why is that?)
• Colouring a dominating set without conflicts: \(q\)-subset square colouring
• Maximal independent sets in a generalisation of caterpillar graph
• Coloring a dominating set without conflicts: \(q\)-subset square coloring

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

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