Premium
Some results on the reconstruction problems. p ‐claw‐free, chordal, and p 4 ‐reducible graphs
Author(s) -
Thatte Bhalchandra D.
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190409
Subject(s) - claw , chordal graph , combinatorics , mathematics , vertex (graph theory) , indifference graph , split graph , discrete mathematics , graph , 1 planar graph , biology , ecology
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.