✦ LIBER ✦

On powers and centers of chordal graphs

✍ Scribed by Renu Laskar; Douglas Shier

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 486 KB
Volume: 6
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(83)90068-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

LexBFS-orderings and powers of chordal g

LexBFS-orderings and powers of chordal graphs

✍ Andreas Brandstädt; Feodor F. Dragan; Falk Nicolai 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 824 KB

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 grap

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

On the pathwidth of chordal graphs

✍ Jens Gusted 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 927 KB

The parallel solution of domination prob

The parallel solution of domination problems on chordal and strongly chordal graphs

✍ Elias Dahlhaus; Peter Damaschke 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 975 KB

On the chordality of a graph

✍ Terry A. McKee; Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 574 KB

## Abstract The __chordality__ of a graph __G__ = (__V, E__) is defined as the minimum __k__ such that we can write __E__ = __E__~1~ ∩ … ∩ __E__~__k__~ with each (__V, E__~__i__~) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result