zbMATH — the first resource for mathematics

On unique independence weighted graphs. (English) Zbl 1232.05162
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 257-264 (2010).
Summary: An independent set in a graph \(G\) is a set of vertices no two of which are joined by an edge. A vertex-weighted graph associates a weight with every vertex in the graph. A vertex-weighted graph \(G\) is called a unique independence vertex-weighted graph if it has a unique independent set with maximum sum of weights.
In this paper we observe that the problem of recognizing unique independence vertex-weighted graphs is NP-hard, and therefore no efficient characterization can be expected in general: we give, however, some combinatorial characterizations of unique independence vertex-weighted graphs.
For the entire collection see [Zbl 1202.05003].
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)