✦ LIBER ✦

Restricted unimodular chordal graphs

✍ Scribed by Peled, Uri N.; Wu, Julin

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 176 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199902)30:2<121::aid-jgt6>3.0.co;2-1

No coin nor oath required. For personal study only.

✦ Synopsis

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 them by starting from block graphs and multiplying vertices subject to a certain restriction, which leads to a linear-time recognition algorithm. We show how they are related to other classes such as distance-hereditary chordal graphs and strongly chordal graphs.

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

Tough enough chordal graphs are Hamilton

Tough enough chordal graphs are Hamiltonian

✍ Chen, Guantao; Jacobson, Michael S.; K�zdy, Andr� E.; Lehel, Jen? 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 2 views

We prove that every 18-tough chordal graph has a Hamiltonian cycle.

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 👁 2 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

Well covered simplicial, chordal, and ci

Well covered simplicial, chordal, and circular arc graphs

✍ Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 2 views

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.

More than one tough chordal planar graph

More than one tough chordal planar graphs are Hamiltonian

✍ B�hme, Thomas; Harant, Jochen; Tk�?, Michal 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 2 views

We prove the result stated in the title. Furthermore, it is proved that for any > 0, there is a 1-tough chordal planar graph G such that the length of a longest cycle of G is less than |V (G )|.

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

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