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.

Review text

The author investigates certain directed graphs associated with the famous ``reconstruction conjecture by \textit{P. J. Kelly} [On isomorphic transformations. University of Wisconsin (PhD Thesis) (1942)] and \textit{S. Ulam} [A collection of mathematical problems. New York and London: Interscience Publishers (1960; Zbl 0086.24101)]. The reconstruction conjecture states that for any graph \(G\) on at least three vertices, the multiset of ``vertex-deleted subgraphs \(\{G - v : v \in V(G)\}\) is unique. An equivalent way of stating the conjecture, which is more technical but relevant to the contents of the paper, is as follows. Given a graph \(G\), say that a graph \(G^\prime\) satisfies property \((\ast)\) if there exists a bijective map \(f: V(G) \rightarrow V(G^\prime)\) such that for any \(v \in V(G)\), there exists a graph isomorphism \(\phi_v: G - v \rightarrow G^\prime - f(v)\). A graph \(G\) is said to be reconstructible if any graph \(G^\prime\) with property \((\ast)\) is isomorphic to \(G\). Then the conjecture states that every graph on at least three vertices is reconstructible. Consider two graphs \(G\), \(G^\prime\), such that \(G^\prime\) satisfies property \((\ast)\), with a bijective map \(f\) and graph isomorphisms \(\{ \phi_v : v \in V(G) \}\). Then, the associated directed graph \(\tilde{G}\) is defined as follows. The vertex set of \(\tilde{G}\) is \(V(G)\). It has two types of directed arrows: normal-arrows and dashed-arrows. There exists a normal-arrow from \(v_1\) to \(v_2\) if and only if \(v_1v_2\) is not an edge in \(G\), but \(f(v_1) \phi_{v_1}(v_2)\) is an edge in \(G^\prime\). There exists a dashed-arrow from \(v_1\) to \(v_2\) if and only if \(f(v_1)f(v_2)\) is not an edge in \(G^\prime\) and \(v_1 \phi^{-1}_{v_1}(f(v_2))\) is an edge in \(G\). The author investigates cases in which reconstructibility can be inferred solely from properties of this associated directed graph. For instance, it is shown that if some vertex in \(\tilde{G}\) has no normal arrows or dashed arrows arising from it, then \(G\) is isomorphic to \(G'\). Finally, many other structural properties from these associated directed graphs are given, for instance, the existence and structure of cycles with alternating normal and dashed arrows.

Recommendations

Cites work

Cited in

(12)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138987)