✦ LIBER ✦

Squares, clique graphs, and chordality

✍ Scribed by W. D. Wallis; Julin Wu

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 427 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200104

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study the squares and the clique graphs of chordal graphs and various special classes of chordal graphs. Chordality conditions for squares and clique graphs are given. Several theorems concering chordal graphs are generalized. © 1996 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

Strong clique trees, neighborhood trees,

Strong clique trees, neighborhood trees, and strongly chordal graphs

✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh

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 .

Distance Approximating Trees for Chordal

Distance Approximating Trees for Chordal and Dually Chordal Graphs

✍ Andreas Brandstädt; Victor Chepoi; Feodor Dragan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a d

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

Self-clique graphs and matrix permutatio

Self-clique graphs and matrix permutations

✍ Adrian Bondy; Guillermo Durán; Min Chih Lin; Jayme L. Szwarcfiter 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

## Abstract The __clique graph__ of a graph is the intersection graph of its (maximal) cliques. A graph is __self‐clique__ when it is isomorphic with its clique graph, and is __clique‐Helly__ when its cliques satisfy the Helly property. We prove that a graph is clique‐Helly and self‐clique if and o