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].

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].

##### MSC:

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