Maximal independent sets in caterpillar graphs

DOI10.1016/J.DAM.2011.10.024MaRDI QIDQ765369zbMATHOpenAlexFDO

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

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)

Recommendations

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

Cites work

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

Cited in

(13)

• Leaf realization problem, caterpillar graphs and prefix normal words
• Coloring a dominating set without conflicts: \(q\)-subset square coloring
• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
• On the number of maximal independent sets of vertices in star-like ladders
• The least Laplacian eigenvalue of the unbalanced unicyclic signed graphs with \(k\) pendant vertices
• Cluster-based energy-efficient secure routing in wireless sensor networks
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• A new sum of graphs and caterpillar trees
• The caterpillar-packing polytope
• Colouring a dominating set without conflicts: \(q\)-subset square colouring
• On the maximum number of maximum independent sets of bipartite graphs
• Maximal independent sets in a generalisation of caterpillar graph
• Maximal independent sets in grid graphs

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)