✦ LIBER ✦

Generating weakly triangulated graphs

✍ Scribed by Hayward, Ryan

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 192 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199601)21:1<67::aid-jgt9>3.0.co;2-k

No coin nor oath required. For personal study only.

✦ Synopsis

We show that a graph is weakly triangulated, or weakly chordal, if and only if it can be generated by starting with a graph with no edges, and repeatedly adding an edge, so that the new edge is not the middle edge of any chordless path with four vertices. This is a corollary of results due to Sritharan and Spinrad, and Hayward, Hoang and Maffray, and a natural analog of a theorem due to Fulkerson and Gross, which states that a graph is triangulated, or chordal, if and only if it can be generated by starting with a graph with no vertices, and repeatedly adding a vertex, so that the new vertex is not the middle vertex of any chordless path with three vertices.

Our result answers the question of whether there exists a composition scheme that generates exactly the class of weakly triangulated graphs. 0 1996 John Wiley & Sons.

📜 SIMILAR VOLUMES

Wing-triangulated graphs are perfect

✍ Hougardy, Stefan; Le, Van Bang; Wagler, Annegret 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

The wing-graph W (G) of a graph G has all edges of G as its vertices; two edges of G are adjacent in W (G) if they are the nonincident edges (called wings) of an induced path on four vertices in G. Hoàng conjectured that if W (G) has no induced cycle of odd length at least five, then G is perfect. A

On the girth of hamiltonian weakly pancy

On the girth of hamiltonian weakly pancyclic graphs

✍ Bollob�s, B�la; Thomason, Andrew 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. In answer to a question of Erdős, we show that a Hamiltonian weakly-pancyclic graph of order n can have girth as large as about 2 n/ log n. In contrast to this, we show that the existence of

Generation of isospectral graphs

✍ Halbeisen, Lorenz; Hungerb�hler, Norbert 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB 👁 1 views

We discuss a discrete version of Sunada's Theorem on isospectral manifolds, which allows the generation of isospectral simple graphs, i.e., nonisomorphic simple graphs that have the same Laplace spectrum. We also consider additional boundary conditions and Buser's transplantation technique applied t

Deza graphs: A generalization of strongl

Deza graphs: A generalization of strongly regular graph

✍ M. Erickson; S. Fernando; W. H. Haemers; D. Hardy; J. Hemmeter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

Simple Markov-chain algorithms for gener

Simple Markov-chain algorithms for generating bipartite graphs and tournaments

✍ Ravi Kannan; Prasad Tetali; Santosh Vempala 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g

A generalized Delaunay triangulation alg

A generalized Delaunay triangulation algorithm with adaptive grid size control

✍ Kumar, K. S. Vasanth ;Babu, A. V. Ramesh ;Seetharamu, K. N. ;Sundararajan, T. ;N 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 1 views

A generalized unstructured mesh generation procedure using Delaunay triangulation has been developed for adaptive ®nite element applications. The main features of the method include: (i) a fast and ecient initial triangulation; (ii) interior node insertion with good control over the grid size and as