✦ LIBER ✦

Equistable graphs

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

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 821 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180307

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An equistable graph is a graph for which the incidence vectors of the maximal stable sets are the 0–1 solutions of a linear equation. A necessary condition and a sufficient condition for equistability are given. They are used to characterize the equistability of various classes of perfect graphs, outerplanar graphs, and pseudothreshold graphs. Some classes of equistable graphs are shown to be closed under graph substitution.

📜 SIMILAR VOLUMES

Equistable chordal graphs

✍ Uri N. Peled; Udi Rotics 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 130 KB

A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We show that a chordal graph is equistable if and only if every two adjacent non-simplicial vertices have a common simplicial

Equistable series–parallel graphs

✍ Ephraim Korach; Uri N. Peled 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 163 KB

A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We characterize those series-parallel graphs that are equistable, generalizing results of Mahadev et al. about equistable out

Complexity results for equistable graphs

Complexity results for equistable graphs and related classes

✍ Martin Milanič; James Orlin; Gábor Rudolf 📂 Article 📅 2010 🏛 Springer US 🌐 English ⚖ 458 KB

A class of threshold and domishold graph

A class of threshold and domishold graphs: equistable and equidominating graphs

✍ Charles Payan 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 484 KB

A thwahold grerph (rtzspativ4y domlshukf graph) is 01 graph for which the independent 881% (rapsctiwzly ths dominuting a&a) cctn bgr chnfuctsrixsd by the 0, l-aolutiona of a linaur ## kpallty (ass [ij and [S]), We define here the #rugher far which the mawlmal indapsndent eettr (rsopsctivsly tha m

On uniform N-equistability

✍ S Rolewicz 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 273 KB

Bistable kinetics of simple reactions on

Bistable kinetics of simple reactions on solid surfaces: lateral interactions, chemical waves, and the equistability criterion

✍ V.P. Zhdanov; B. Kasemo 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 990 KB