𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs whose powers are chordal and graphs whose powers are interval graphs

✍ Scribed by Flotow, Carsten

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
127 KB
Volume
24
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 sufficient for chordality of G 2m .

Similar conditions on G that are sufficient for G m being an interval graph are also obtained.

In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for G m being chordal or interval graph.

πŸ“œ SIMILAR VOLUMES

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.

Powers of Hamiltonian paths in interval
Powers of Hamiltonian paths in interval graphs
✍ Isaak, Garth πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 232 KB πŸ‘ 1 views

We give a simple proof that the obvious necessary conditions for a graph to contain the k th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We wi

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