𝔖 Bobbio Scriptorium
✦   LIBER   ✦

LexBFS-orderings and powers of chordal graphs

✍ Scribed by Andreas Brandstädt; Feodor F. Dragan; Falk Nicolai

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
824 KB
Volume
171
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For an undirected graph G the kth power G k of G is the graph with the same vertex set as G where two vertices are adjacent iff their distance is at most k in G. In this paper we prove that any LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Moreover, we characterize those chordal graphs by forbidden isometric subgraphs for which any LexBFS-ordering of the graph is a common perfect elimination ordering of all powers. For MCS-orderings of chordal graphs the situation is worse: even for trees MCS does not give a common perfect elimination ordering of powers.

📜 SIMILAR VOLUMES

Perfect elimination orderings of chordal
Perfect elimination orderings of chordal powers of graphs
✍ Andreas Brandstädt; Victor D. Chepoi; Feodor F. Dragan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 378 KB

Let G = (V,E) be a finite undirected connected graph. We show that there is a common perfect elimination ordering of all powers of G which represent chordal graphs. Consequently, if G and all of its powers are chordal then all these graphs admit a common perfect elimination ordering. Such an orderin

Graphs whose powers are chordal and grap
Graphs whose powers are chordal and graphs whose powers are interval graphs
✍ Flotow, Carsten 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 3 views

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G m . This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is suffi

Generating and characterizing the perfec
Generating and characterizing the perfect elimination orderings of a chordal graph
✍ L.S. Chandran; L. Ibarra; F. Ruskey; J. Sawada 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 402 KB

We develop a constant time transposition "oracle" for the set of perfect elimination orderings of chordal graphs. Using this oracle, we can generate a Gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. Using clique trees, we show how the