𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture of wang and williams

✍ Scribed by N. V. R. Mahadev; Uri N. Peled

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
210 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

On a conjecture of Thomassen and Toft
On a conjecture of Thomassen and Toft
✍ Kriesell, Matthias 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

This article is motivated by a conjecture of Thomassen and Toft on the number s 2 (G) of separating vertex sets of cardinality 2 and the number v 2 (G) of vertices of degree 2 in a graph G belonging to the class G of all 2-connected graphs without nonseparating induced cycles. Let G denote the numbe

On a conjecture of bollobás and bosák
On a conjecture of bollobás and bosák
✍ Štefan Znám 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB

## Abstract It is shown that, for all sufficiently large __k__, the complete graph __K~n~__ can be decomposed into __k__ factors of diameter 2 if and only if __n__ ≥ 6__k__.