## Abstract

For a fixed positive integer k, a set S of vertices of a graph or multigraph is called a k-independent set if the subgraph induced by S has maximum degree less than k. The well-known algorithm MAX finds a maximal k-independent set in a graph or multigraph by iteratively removing vertices of maximum degree until what remains has maximum degree less than k. We give an efficient procedure that determines, for a given degree sequence D, the smallest cardinality b(D) of a k-independent set that can result from any application of MAX to any loopless multigraph with degree sequence D. This analysis of the worst case is sharp for each degree sequence D in that there exists a multigraph G with degree sequence D such that some application of MAX to G will result in a k-independent set of cardinality exactly b(D).

Original language | English |
---|---|

Pages (from-to) | 56-68 |

Number of pages | 13 |

Journal | Discrete Applied Mathematics |

Volume | 265 |

DOIs | |

Publication status | Published - 1 Jan 2019 |

## Keywords

- k-independent set
- MAX algorithm
- Pair covering