✦ LIBER ✦
Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs
✍ Scribed by Bhalchandra D. Thatte
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 507 KB
- Volume
- 19
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A claw is an induced subgraph isomorphic to K~1,3.~ The claw‐point is the point of degree 3 in a claw. A graph is called p‐claw‐free when no p‐cycle has a claw‐point on it. It is proved that for p ≥ 4, p‐claw‐free graphs containting at least one chordless p‐cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw‐free graphs. A simple proof of vertex reconstructibility of P~4~‐reducible graphs is also presented. © 1995 John Wiley & Sons, Inc.