Reconstructibility and perfect graphs

✍ Scribed by Michael Von Rimscha

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 738 KB
• Volume: 47
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90099-7

✦ Synopsis

It is shown that the following classes of graphs are recognizable (i.e. looking at the point-deleted subgraphs of a graph G one can decide whether G belongs to that class or not): (1) perfect graphs, (2) triangulated graphs, (3) interval graphs, (4) comparability graphs, (5) split graphs. Furthermore we show the reconstructibility of (1) threshold graphs, (2) split graphs G, for which holds o(G) + o(G) = ICI+ 1, (3) split graphs, which are in addition comparability graphs, (4) unit interval graphs. 0. Formal&m A graph G is an ordered pair of a finite set of vertices V(G) and a set of edges E(G) consisting of two-element subsets of V(G). Thus we speak about undirected graphs without loops and multiple edges. If XC V(G), then X denotes the subgraph induced by X. Let x E V(G); G, is defined to be the subgraph induced by V(G)(x).

IG] is the number of vertices of G.

H is a reconstruction of G, if there exists a bijection 4 from V(G) onto V(H) such that G, is isomorphic to I+&) for every x E V(G). G is reconstructible, if every reconstruction of G is isomorphic to G. A class K of graphs is recognizable, if every reconstruction of a G E K belongs to K too. A parameter p is reconstructible, if for each graph G all reconstructions of G take the same value for p as G does.

If not stated otherwise, we use the definitions of [4].

All theorems below refer to graphs with more than 2 vertices.