Well-Covered Graphs: A Survey

Abstract

A graph G is well-covered (or w-c) if every maximal independent set of points in G is also maximum. Clearly, this is equivalent to the property that the greedy algorithm for constructing a maximal independent set always results in a maximum independent set. Although the problem of independence number is well-known to be NP-complete, it is trivially polynomial for well covered graphs. The concept of well-coveredness was introduced by the author in PI and was first discussed therein with respect to its relationship to a number of other properties involving the independence number. Since then, a number of results about well-covered graphs have been obtained. It is our purpose in this paper to survey these results for the first time. As the reader will see, many of the results we will discuss are quite recent and have not as yet appeared in print.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA247861

Entities

People

  • Michael D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Families (Human)
  • Graph Theory
  • Inequalities
  • Mathematics
  • New York
  • Numbers
  • Polynomials
  • Real Numbers
  • Recognition
  • Sequences
  • Triangles

Readers

  • Geodesy
  • Microbial Pathology
  • Operations Research