𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Equistable series–parallel graphs

✍ Scribed by Ephraim Korach; Uri N. Peled

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
163 KB
Volume
132
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 outer-planar graphs.

📜 SIMILAR VOLUMES

Equistable graphs
Equistable graphs
✍ N. V. R. Mahadev; Uri N. Peled; Feng Sun 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 821 KB

## 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 perfe

Equistable chordal graphs
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

Chromaticity of series-parallel graphs
Chromaticity of series-parallel graphs
✍ K.M. Koh; C.P. Teo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 454 KB

By applying a sequence of edge-gluings on a set of cycles each of length k, we obtain a special series-parallel graph. The well-known k-gon tree theorem (see [l, lo]) states that these graphs form a X-equivalence class. Many of the other known classes of X-unique graphs and X-equivalence classes are

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

Series-parallel graphs: A logical approa
Series-parallel graphs: A logical approach
✍ T. A. McKee 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 297 KB

The notions "series-parallel" and "nonseparable" are shown to be logical converses of each other when formulated in a particular dual-like fashion. Self-dual circuitkutset characterizations are given of series-parallel and of series-parallel nonseparable graphs.