The reconstruction conjecture for finite simple graphs and associated directed graphs

Abstract: In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let

G a m m a

and

G a m m a^{'}

be finite simple graphs with at least three vertices such that there exists a bijective map

f : V (G a m m a) i g h t a r r o w V (G a m m a^{'})

and for any

v i n V (G a m m a)

, there exists an isomorphism

p h i_{v} : G a m m a - v o G a m m a^{'} - f (v)

. Then we define the associated directed graph

w i d e t i l d e G a m m a = w i d e t i l d e G a m m a (G a m m a, G a m m a^{'}, f, {p h i_{v}}_{v i n V (G a m m a)})

with two kinds of arrows from the graphs

G a m m a

and

G a m m a^{'}

, the bijective map

f

and the isomorphisms

{p h i_{v}}_{v i n V (G a m m a)}

. By investigating the associated directed graph

w i d e t i l d e G a m m a

, we study when are the two graphs

G a m m a

and

G a m m a^{'}

isomorphic.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: The reconstruction conjecture for finite simple graphs and associated directed graphs