✦ LIBER ✦

Equistable chordal graphs

✍ Scribed by Uri N. Peled; Udi Rotics

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 130 KB
Volume: 132
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00401-3

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 show that a chordal graph is equistable if and only if every two adjacent non-simplicial vertices have a common simplicial neighbor. ?

📜 SIMILAR VOLUMES

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

Strongly chordal and chordal bipartite g

Strongly chordal and chordal bipartite graphs are

✍ Pinar Heggernes; Federico Mancini; Charis Papadopoulos; R. Sritharan 📂 Article 📅 2010 🏛 Springer US 🌐 English ⚖ 634 KB

Chordal graphs, interval graphs, and wqo

✍ Ding, Guoli 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB 👁 1 views

Let be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by . On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by .

Restricted unimodular chordal graphs

✍ Peled, Uri N.; Wu, Julin 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 1 views

A chordal graph is called restricted unimodular if each cycle of its vertex-clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct t

Centers of chordal graphs

✍ Gerard J. Chang 📂 Article 📅 1991 🏛 Springer Japan 🌐 English ⚖ 505 KB