Maximal independent sets in a generalisation of caterpillar graph

DOI10.1007/S10878-015-9960-0zbMATH Open1365.90229arXiv1502.04514OpenAlexW3102753258MaRDI QIDQ512892FDOQ512892

Sanjeev Saxena, K. S. Neethi

Publication date: 3 March 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: A caterpillar graph is a tree which on removal of all its pendant vertices leaves a chordless path. The chordless path is called the backbone of the graph. The edges from the backbone to the pendant vertices are called the hairs of the caterpillar graph. Ortiz and Villanueva (C.Ortiz and M.Villanueva, Discrete Applied Mathematics, 160(3): 259-266, 2012) describe an algorithm, linear in the size of the output, for finding a family of maximal independent sets in a caterpillar graph. In this paper, we propose an algorithm, again linear in the output size, for a generalised caterpillar graph, where at each vertex of the backbone, there can be any number of hairs of length one and at most one hair of length two.

Full work available at URL: https://arxiv.org/abs/1502.04514

Recommendations

• Maximal independent sets in caterpillar graphs
• scientific article; zbMATH DE number 2188328
• On caterpillar factors in graphs
• Caterpillar arboricity of planar graphs
• Maximizing the algebraic connectivity for a subclass of caterpillars

zbMATH Keywords

maximal independent setcaterpillar graphsgeneralised caterpillar graphsgenerating all MISMIS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• The complexity of computing the permanent
• A New Algorithm for Generating All the Maximal Independent Sets
• The number of caterpillars
• Graph Drawing
• Maximal independent sets in caterpillar graphs

Cited In (1)

• The Ultimate Categorical Independence Ratio of Complete Multipartite Graphs

This page was built for publication: Maximal independent sets in a generalisation of caterpillar graph

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