MAX for k-independence in multigraphs

DOI10.1016/J.DAM.2019.03.007MaRDI QIDQ2312650zbMATH OpenOpenAlexFDO

Authors Nevena Francetić, Sara Herke, Daniel Horsley

Publication date 17 July 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-independent setMAX algorithmpair covering

Mathematics Subject Classification ID

Vertex degrees (05C07) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

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)$.

Recommendations

• Maximal k-independent sets in graphs
• A generalization of maximal independent sets
• Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
• Graphs with given k-independence number
• New approach to the \(k\)-independence number of a graph

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A note on greedy algorithms for the maximum weighted independent set problem
• Degree sequences of graphs and dominance order
• Extending the MAX algorithm for maximum independent set
• Generalising Fisher's inequality to coverings and packings
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 4121429 (Why is no real title available?)
• Improved lower bounds on k‐independence
• Independence and the Havel-Hakimi residue
• k-Independence and thek-residue of a graph
• Lower bounds on the independence number in terms of the degrees
• New approach to the \(k\)-independence number of a graph
• New results on \(k\)-independence of graphs
• On coverings
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On sequential heuristic methods for the maximum independent set problem
• On the k-residue of disjoint unions of graphs with applications to k-independence
• On the residue of a graph
• The independence number of graphs in terms of degrees
• The potential of greed for independence

Cited in

(1)

• A generalization of maximal independent sets

This page was built for publication: MAX for \(k\)-independence in multigraphs

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