Premium
On a conjecture of wang and williams
Author(s) -
Mahadev N. V. R.,
Peled Uri N.
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150203
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , converse , graph , discrete mathematics , geometry
Wang and Williams defined a threshold assignment for a graph G as an assignment of a non‐negative weight to each vertex and edge of G , and a threshold t , such that a set S of vertices is stable if and only if the total weight of the subgraph induced by S does not exceed t ‐ 1. This is always possible with zero vertex‐weights, unit edge‐weights, and t = 1. By definition, a threshold graph is a graph having a threshold assignment with zero edge‐weights. The threshold weight of G is the minimum total edgeweight of a threshold assignment of G. A graph G = ( V,E ) is called heavy if its threshold weight is | E |. A clique C of G is called big if | E ( C )| > | E ( G ‐ C )|. Wang and Williams showed that graphs with a big clique are not heavy, and conjectured the converse. They verified the conjecture for triangle‐free graphs. We disprove the conjecture in general, but prove it for perfect graphs.