✦ LIBER ✦

Perfect Elimination and Chordal Bipartite Graphs

✍ Scribed by Martin Charles Golumbic; Clinton F. Goss

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 348 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020209

No coin nor oath required. For personal study only.

✦ Synopsis

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 sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.

📜 SIMILAR VOLUMES

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 .

Squares, clique graphs, and chordality

✍ W. D. Wallis; Julin Wu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB

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

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

Finding all minimum-cost perfect matchin

Finding all minimum-cost perfect matchings in Bipartite graphs

✍ Komei Fukuda; Tomomi Matsui 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 401 KB

A Family of Perfect Factorisations of Co

A Family of Perfect Factorisations of Complete Bipartite Graphs

✍ Darryn Bryant; Barbara M. Maenhaut; Ian M. Wanless 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 493 KB

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n=p 2 for an odd prime p. We construct a family of ( p -1)/2 non-isomorphic perfect 1-factorisations of K n, n . Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin s

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