✦ LIBER ✦

Perfect elimination orderings of chordal powers of graphs

✍ Scribed by Andreas Brandstädt; Victor D. Chepoi; Feodor F. Dragan

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 378 KB
Volume: 158
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00081-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 ordering can be computed in 0( 1 V/ . (El) t' lme using a generalization of the Tarjan and Yannakakis' Maximum Cardinality Search.

Recently, powers of graphs from several classes have been investigated. One of the first results on powers of graphs is due to Duchet [5]: If Gk is chordal then also Gk+2. In particular, odd powers of chordal graphs are chordal, whereas even powers ' Second and third author supported by the VW-Stiftung Project No. I/69041.

📜 SIMILAR VOLUMES

New linear time algorithms for generatin

New linear time algorithms for generating perfect elimination orderings of chordal graphs

✍ B.S. Panda 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Perfect Elimination and Chordal Bipartit

Perfect Elimination and Chordal Bipartite Graphs

✍ Martin Charles Golumbic; Clinton F. Goss 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on spars

Computing a perfect edge without vertex

Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph

✍ T. Kloks; D. Kratsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 473 KB

A generalization of chordal graphs

✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

Vertex partitions of chordal graphs

✍ David R. Wood 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into ‘bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro

Chordal Completions of Planar Graphs

✍ F.R.K. Chung; D. Mumford 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 431 KB

We prove that every planar graph on \(n\) vertices is contained in a chordal graph with at most \(c n \log n\) edges for some abolsute constant \(c\) and this is best possible to within a constant factor. 1994 Academic Press, Inc.