MAX for k-independence in multigraphs

Nevena Francetić, Sara Herke, Daniel Horsley

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)56-68
Number of pages13
JournalDiscrete Applied Mathematics
Volume265
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • k-independent set
  • MAX algorithm
  • Pair covering

Cite this