Combinatorical and Algebraic Structures Seminar

Date:	6.1.2009
Speaker:	Angela Mestre, Doppler Institute
Title:	On the vertex and edge reconstruction conjectures
Abstract:	We review the well known vertex-reconstruction and edge-reconstruction conjectures due to S. Ulam and F. Harary, respectively. They state that every graph $G=(V,E)$ (resp. every simple graph $G=(V,E)$) with at least three vertices (resp. four edges) is uniquely constructed by the set of vertex-erased graphs $\{G-v: v \in V\}$ (resp. edge-erased graphs $\{G-e: e\in E\}$). Moreover, we express the multiplicities of the vertex-erased graphs $G-v$ (resp. edge erased-graphs $G-e$) in terms of the orders of the groups of automorphisms of the graphs $G$ and $G-v$ (resp. $G-e$), and give some examples.

Return to index.

last update: 27.9.2007, webmaster: Petr Ambrož